aboutsummaryrefslogtreecommitdiffstats
path: root/gcc-4.2.1-5666.3/gcc/tree-data-ref.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/tree-data-ref.c')
-rw-r--r--gcc-4.2.1-5666.3/gcc/tree-data-ref.c4495
1 files changed, 0 insertions, 4495 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/tree-data-ref.c b/gcc-4.2.1-5666.3/gcc/tree-data-ref.c
deleted file mode 100644
index 75b57392a..000000000
--- a/gcc-4.2.1-5666.3/gcc/tree-data-ref.c
+++ /dev/null
@@ -1,4495 +0,0 @@
-
-/* Data references and dependences detectors.
- Copyright (C) 2003, 2004, 2005, 2006 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 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, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, 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 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 "tm.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"
-
-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 tree object_analysis (tree, tree, bool, struct data_reference **,
- tree *, tree *, tree *, tree *, tree *,
- struct ptr_info_def **, subvar_t *);
-static struct data_reference * init_data_ref (tree, tree, tree, tree, bool,
- tree, tree, tree, tree, tree,
- struct ptr_info_def *,
- enum data_ref_type);
-static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
- struct data_reference *,
- struct data_reference *);
-
-/* Determine if PTR and DECL may alias, the result is put in ALIASED.
- Return FALSE if there is no symbol memory tag for PTR. */
-
-static bool
-ptr_decl_may_alias_p (tree ptr, tree decl,
- struct data_reference *ptr_dr,
- bool *aliased)
-{
- tree tag = NULL_TREE;
- struct ptr_info_def *pi = DR_PTR_INFO (ptr_dr);
-
- gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
-
- if (pi)
- tag = pi->name_mem_tag;
- if (!tag)
- tag = get_var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
- if (!tag)
- tag = DR_MEMTAG (ptr_dr);
- if (!tag)
- return false;
-
- *aliased = is_aliased_with (tag, decl);
- return true;
-}
-
-
-/* Determine if two pointers may alias, the result is put in ALIASED.
- Return FALSE if there is no symbol memory tag for one of the pointers. */
-
-static bool
-ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
- struct data_reference *dra,
- struct data_reference *drb,
- bool *aliased)
-{
- tree tag_a = NULL_TREE, tag_b = NULL_TREE;
- struct ptr_info_def *pi_a = DR_PTR_INFO (dra);
- struct ptr_info_def *pi_b = DR_PTR_INFO (drb);
-
- if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag)
- {
- tag_a = pi_a->name_mem_tag;
- tag_b = pi_b->name_mem_tag;
- }
- else
- {
- tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->symbol_mem_tag;
- if (!tag_a)
- tag_a = DR_MEMTAG (dra);
- if (!tag_a)
- return false;
-
- tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->symbol_mem_tag;
- if (!tag_b)
- tag_b = DR_MEMTAG (drb);
- if (!tag_b)
- return false;
- }
-
- if (tag_a == tag_b)
- *aliased = true;
- else
- *aliased = may_aliases_intersect (tag_a, tag_b);
-
- return true;
-}
-
-
-/* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
- Return FALSE if there is no symbol memory tag for one of the symbols. */
-
-static bool
-may_alias_p (tree base_a, tree base_b,
- struct data_reference *dra,
- struct data_reference *drb,
- bool *aliased)
-{
- if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
- {
- if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
- {
- *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
- return true;
- }
- if (TREE_CODE (base_a) == ADDR_EXPR)
- return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb,
- aliased);
- else
- return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra,
- aliased);
- }
-
- return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
-}
-
-
-/* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
- are not aliased. Return TRUE if they differ. */
-static bool
-record_ptr_differ_p (struct data_reference *dra,
- struct data_reference *drb)
-{
- bool aliased;
- tree base_a = DR_BASE_OBJECT (dra);
- tree base_b = DR_BASE_OBJECT (drb);
-
- if (TREE_CODE (base_b) != COMPONENT_REF)
- return false;
-
- /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
- For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
- Probably will be unnecessary with struct alias analysis. */
- while (TREE_CODE (base_b) == COMPONENT_REF)
- base_b = TREE_OPERAND (base_b, 0);
- /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
- ((*q)[i]). */
- if (TREE_CODE (base_a) == INDIRECT_REF
- && ((TREE_CODE (base_b) == VAR_DECL
- && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra,
- &aliased)
- && !aliased))
- || (TREE_CODE (base_b) == INDIRECT_REF
- && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
- TREE_OPERAND (base_b, 0), dra, drb,
- &aliased)
- && !aliased))))
- return true;
- else
- return false;
-}
-
-/* Determine if two record/union accesses are aliased. Return TRUE if they
- differ. */
-static bool
-record_record_differ_p (struct data_reference *dra,
- struct data_reference *drb)
-{
- bool aliased;
- tree base_a = DR_BASE_OBJECT (dra);
- tree base_b = DR_BASE_OBJECT (drb);
-
- if (TREE_CODE (base_b) != COMPONENT_REF
- || TREE_CODE (base_a) != COMPONENT_REF)
- return false;
-
- /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
- For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
- Probably will be unnecessary with struct alias analysis. */
- while (TREE_CODE (base_b) == COMPONENT_REF)
- base_b = TREE_OPERAND (base_b, 0);
- while (TREE_CODE (base_a) == COMPONENT_REF)
- base_a = TREE_OPERAND (base_a, 0);
-
- if (TREE_CODE (base_a) == INDIRECT_REF
- && TREE_CODE (base_b) == INDIRECT_REF
- && ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
- TREE_OPERAND (base_b, 0),
- dra, drb, &aliased)
- && !aliased)
- return true;
- else
- return false;
-}
-
-/* Determine if an array access (BASE_A) and a record/union access (BASE_B)
- are not aliased. Return TRUE if they differ. */
-static bool
-record_array_differ_p (struct data_reference *dra,
- struct data_reference *drb)
-{
- bool aliased;
- tree base_a = DR_BASE_OBJECT (dra);
- tree base_b = DR_BASE_OBJECT (drb);
-
- if (TREE_CODE (base_b) != COMPONENT_REF)
- return false;
-
- /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
- For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
- Probably will be unnecessary with struct alias analysis. */
- while (TREE_CODE (base_b) == COMPONENT_REF)
- base_b = TREE_OPERAND (base_b, 0);
-
- /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
- (a[i]). In case of p->c[i] use alias analysis to verify that p is not
- pointing to a. */
- if (TREE_CODE (base_a) == VAR_DECL
- && (TREE_CODE (base_b) == VAR_DECL
- || (TREE_CODE (base_b) == INDIRECT_REF
- && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb,
- &aliased)
- && !aliased))))
- return true;
- else
- return false;
-}
-
-
-/* Determine if an array access (BASE_A) and a pointer (BASE_B)
- are not aliased. Return TRUE if they differ. */
-static bool
-array_ptr_differ_p (tree base_a, tree base_b,
- struct data_reference *drb)
-{
- bool aliased;
-
- /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
- help of alias analysis that p is not pointing to a. */
- if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF
- && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
- && !aliased))
- return true;
- else
- return false;
-}
-
-
-/* This is the simplest data dependence test: determines whether the
- data references A and B access the same array/region. Returns
- false when the property is not computable at compile time.
- Otherwise return true, and DIFFER_P will record the result. This
- utility will not be necessary when alias_sets_conflict_p will be
- less conservative. */
-
-static bool
-base_object_differ_p (struct data_reference *a,
- struct data_reference *b,
- bool *differ_p)
-{
- tree base_a = DR_BASE_OBJECT (a);
- tree base_b = DR_BASE_OBJECT (b);
- bool aliased;
-
- if (!base_a || !base_b)
- return false;
-
- /* Determine if same base. Example: for the array accesses
- a[i], b[i] or pointer accesses *a, *b, bases are a, b. */
- if (base_a == base_b)
- {
- *differ_p = false;
- return true;
- }
-
- /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
- and (*q) */
- if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
- && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
- {
- *differ_p = false;
- return true;
- }
-
- /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */
- if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
- && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
- && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
- {
- *differ_p = false;
- return true;
- }
-
-
- /* Determine if different bases. */
-
- /* At this point we know that base_a != base_b. However, pointer
- accesses of the form x=(*p) and y=(*q), whose bases are p and q,
- may still be pointing to the same base. In SSAed GIMPLE p and q will
- be SSA_NAMES in this case. Therefore, here we check if they are
- really two different declarations. */
- if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
- {
- *differ_p = true;
- return true;
- }
-
- /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
- help of alias analysis that p is not pointing to a. */
- if (array_ptr_differ_p (base_a, base_b, b)
- || array_ptr_differ_p (base_b, base_a, a))
- {
- *differ_p = true;
- return true;
- }
-
- /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
- help of alias analysis they don't point to the same bases. */
- if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
- && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b,
- &aliased)
- && !aliased))
- {
- *differ_p = true;
- return true;
- }
-
- /* Compare two record/union bases s.a and t.b: s != t or (a != b and
- s and t are not unions). */
- if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
- && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
- && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
- && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
- || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
- && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
- && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
- {
- *differ_p = true;
- return true;
- }
-
- /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
- ((*q)[i]). */
- if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
- {
- *differ_p = true;
- return true;
- }
-
- /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
- (a[i]). In case of p->c[i] use alias analysis to verify that p is not
- pointing to a. */
- if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
- {
- *differ_p = true;
- return true;
- }
-
- /* Compare two record/union accesses (b.c[i] or p->c[i]). */
- if (record_record_differ_p (a, b))
- {
- *differ_p = true;
- return true;
- }
-
- return false;
-}
-
-/* Function base_addr_differ_p.
-
- This is the simplest data dependence test: determines whether the
- data references DRA and DRB access the same array/region. Returns
- false when the property is not computable at compile time.
- Otherwise return true, and DIFFER_P will record the result.
-
- The algorithm:
- 1. if (both DRA and DRB are represented as arrays)
- compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
- 2. else if (both DRA and DRB are represented as pointers)
- try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
- 3. else if (DRA and DRB are represented differently or 2. fails)
- only try to prove that the bases are surely different
-*/
-
-static bool
-base_addr_differ_p (struct data_reference *dra,
- struct data_reference *drb,
- bool *differ_p)
-{
- tree addr_a = DR_BASE_ADDRESS (dra);
- tree addr_b = DR_BASE_ADDRESS (drb);
- tree type_a, type_b;
- bool aliased;
-
- if (!addr_a || !addr_b)
- return false;
-
- type_a = TREE_TYPE (addr_a);
- type_b = TREE_TYPE (addr_b);
-
- gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
-
- /* 1. if (both DRA and DRB are represented as arrays)
- compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */
- if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
- return base_object_differ_p (dra, drb, differ_p);
-
- /* 2. else if (both DRA and DRB are represented as pointers)
- try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */
- /* If base addresses are the same, we check the offsets, since the access of
- the data-ref is described by {base addr + offset} and its access function,
- i.e., in order to decide whether the bases of data-refs are the same we
- compare both base addresses and offsets. */
- if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
- && (addr_a == addr_b
- || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
- && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
- {
- /* Compare offsets. */
- tree offset_a = DR_OFFSET (dra);
- tree offset_b = DR_OFFSET (drb);
-
- STRIP_NOPS (offset_a);
- STRIP_NOPS (offset_b);
-
- /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
- PLUS_EXPR. */
- if (offset_a == offset_b
- || (TREE_CODE (offset_a) == MULT_EXPR
- && TREE_CODE (offset_b) == MULT_EXPR
- && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
- && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
- {
- *differ_p = false;
- return true;
- }
- }
-
- /* 3. else if (DRA and DRB are represented differently or 2. fails)
- only try to prove that the bases are surely different. */
-
- /* Apply alias analysis. */
- if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
- {
- *differ_p = true;
- return true;
- }
-
- /* An instruction writing through a restricted pointer is "independent" of any
- instruction reading or writing through a different pointer, in the same
- block/scope. */
- else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
- || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
- {
- *differ_p = true;
- return true;
- }
- return false;
-}
-
-/* Returns true iff A divides B. */
-
-static inline bool
-tree_fold_divides_p (tree a,
- tree b)
-{
- /* Determines whether (A == gcd (A, B)). */
- return tree_int_cst_equal (a, tree_fold_gcd (a, b));
-}
-
-/* Returns true iff A divides B. */
-
-static inline bool
-int_divides_p (int a, int b)
-{
- return ((b % a) == 0);
-}
-
-
-
-/* Dump into FILE all the data references from DATAREFS. */
-
-void
-dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
-{
- unsigned int i;
- struct data_reference *dr;
-
- for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
- dump_data_reference (file, dr);
-}
-
-/* Dump into FILE all the dependence relations from DDRS. */
-
-void
-dump_data_dependence_relations (FILE *file,
- VEC (ddr_p, heap) *ddrs)
-{
- unsigned int i;
- struct data_dependence_relation *ddr;
-
- for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
- dump_data_dependence_relation (file, ddr);
-}
-
-/* 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 stmt: ");
- print_generic_stmt (outf, DR_STMT (dr), 0);
- fprintf (outf, " ref: ");
- print_generic_stmt (outf, DR_REF (dr), 0);
- fprintf (outf, " base_object: ");
- print_generic_stmt (outf, DR_BASE_OBJECT (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 SUBSCRIPT structure. */
-
-void
-dump_subscript (FILE *outf, struct subscript *subscript)
-{
- tree chrec = SUB_CONFLICTS_IN_A (subscript);
-
- fprintf (outf, "\n (subscript \n");
- 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 (subscript);
- fprintf (outf, " last_conflict: ");
- 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 (subscript);
- fprintf (outf, " last_conflict: ");
- print_generic_stmt (outf, last_iteration, 0);
- }
-
- fprintf (outf, " (Subscript distance: ");
- print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
- fprintf (outf, " )\n");
- fprintf (outf, " )\n");
-}
-
-/* Print the classic direction vector DIRV to OUTF. */
-
-void
-print_direction_vector (FILE *outf,
- lambda_vector dirv,
- int length)
-{
- int eq;
-
- for (eq = 0; eq < length; eq++)
- {
- enum data_dependence_direction dir = 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. */
-
-void
-print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
- int length)
-{
- unsigned j;
- lambda_vector v;
-
- for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
- print_direction_vector (outf, v, length);
-}
-
-/* Print a vector of distance vectors. */
-
-void
-print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
- int length)
-{
- unsigned j;
- lambda_vector v;
-
- for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
- print_lambda_vector (outf, v, length);
-}
-
-/* Debug version. */
-
-void
-debug_data_dependence_relation (struct data_dependence_relation *ddr)
-{
- dump_data_dependence_relation (stderr, ddr);
-}
-
-/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
-
-void
-dump_data_dependence_relation (FILE *outf,
- struct data_dependence_relation *ddr)
-{
- struct data_reference *dra, *drb;
-
- dra = DDR_A (ddr);
- drb = DDR_B (ddr);
- fprintf (outf, "(Data Dep: \n");
- if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
- fprintf (outf, " (don't know)\n");
-
- else 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;
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); 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);
- dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
- }
-
- fprintf (outf, " loop nest: (");
- for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
- 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");
-}
-
-/* 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;
- }
-}
-
-/* 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. */
-
-void
-dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
-{
- unsigned int i, j;
- struct data_dependence_relation *ddr;
- lambda_vector v;
-
- for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
- {
- for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
- {
- fprintf (file, "DISTANCE_V (");
- print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
- fprintf (file, ")\n");
- }
-
- for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
- {
- 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. */
-
-void
-dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
-{
- unsigned int i;
- struct data_dependence_relation *ddr;
-
- for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
- dump_data_dependence_relation (file, ddr);
-
- fprintf (file, "\n\n");
-}
-
-
-
-/* Estimate the number of iterations from the size of the data and the
- access functions. */
-
-static void
-estimate_niter_from_size_of_data (struct loop *loop,
- tree opnd0,
- tree access_fn,
- tree stmt)
-{
- tree estimation = NULL_TREE;
- tree array_size, data_size, element_size;
- tree init, step;
-
- init = initial_condition (access_fn);
- step = evolution_part_in_loop_num (access_fn, loop->num);
-
- array_size = TYPE_SIZE (TREE_TYPE (opnd0));
- element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
- if (array_size == NULL_TREE
- || TREE_CODE (array_size) != INTEGER_CST
- || TREE_CODE (element_size) != INTEGER_CST)
- return;
-
- data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
- array_size, element_size);
-
- if (init != NULL_TREE
- && step != NULL_TREE
- && TREE_CODE (init) == INTEGER_CST
- && TREE_CODE (step) == INTEGER_CST)
- {
- tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step);
- tree sign = fold_binary (GT_EXPR, boolean_type_node, i_plus_s, init);
-
- if (sign == boolean_true_node)
- estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
- fold_build2 (MINUS_EXPR, integer_type_node,
- data_size, init), step);
-
- /* When the step is negative, as in PR23386: (init = 3, step =
- 0ffffffff, data_size = 100), we have to compute the
- estimation as ceil_div (init, 0 - step) + 1. */
- else if (sign == boolean_false_node)
- estimation =
- fold_build2 (PLUS_EXPR, integer_type_node,
- fold_build2 (CEIL_DIV_EXPR, integer_type_node,
- init,
- fold_build2 (MINUS_EXPR, unsigned_type_node,
- integer_zero_node, step)),
- integer_one_node);
-
- if (estimation)
- record_estimate (loop, estimation, boolean_true_node, stmt);
- }
-}
-
-/* Given an ARRAY_REF node REF, records its access functions.
- Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
- i.e. the constant "3", then recursively call the function on opnd0,
- i.e. the ARRAY_REF "A[i]".
- If ESTIMATE_ONLY is true, we just set the estimated number of loop
- iterations, we don't store the access function.
- The function returns the base name: "A". */
-
-static tree
-analyze_array_indexes (struct loop *loop,
- VEC(tree,heap) **access_fns,
- tree ref, tree stmt,
- bool estimate_only)
-{
- 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));
-
- if (estimate_only
- && chrec_contains_undetermined (loop->estimated_nb_iterations))
- estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
-
- if (!estimate_only)
- VEC_safe_push (tree, heap, *access_fns, access_fn);
-
- /* Recursively record other array access functions. */
- if (TREE_CODE (opnd0) == ARRAY_REF)
- return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only);
-
- /* Return the base name of the data access. */
- else
- return opnd0;
-}
-
-/* For an array reference REF contained in STMT, attempt to bound the
- number of iterations in the loop containing STMT */
-
-void
-estimate_iters_using_array (tree stmt, tree ref)
-{
- analyze_array_indexes (loop_containing_stmt (stmt), NULL, ref, stmt,
- true);
-}
-
-/* For a data reference REF contained in the statement 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;
- VEC(tree,heap) *acc_fns;
-
- 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 = XNEW (struct data_reference);
-
- DR_STMT (res) = stmt;
- DR_REF (res) = ref;
- acc_fns = VEC_alloc (tree, heap, 3);
- DR_BASE_OBJECT (res) = analyze_array_indexes
- (loop_containing_stmt (stmt), &acc_fns, ref, stmt, false);
- DR_TYPE (res) = ARRAY_REF_TYPE;
- DR_SET_ACCESS_FNS (res, acc_fns);
- DR_IS_READ (res) = is_read;
- DR_BASE_ADDRESS (res) = NULL_TREE;
- DR_OFFSET (res) = NULL_TREE;
- DR_INIT (res) = NULL_TREE;
- DR_STEP (res) = NULL_TREE;
- DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
- DR_MEMTAG (res) = NULL_TREE;
- DR_PTR_INFO (res) = NULL;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-
- return res;
-}
-
-/* Analyze an indirect memory reference, REF, that comes from STMT.
- IS_READ is true if this is an indirect load, and false if it is
- an indirect store.
- Return a new data reference structure representing the indirect_ref, or
- NULL if we cannot describe the access function. */
-
-static struct data_reference *
-analyze_indirect_ref (tree stmt, tree ref, bool is_read)
-{
- struct loop *loop = loop_containing_stmt (stmt);
- tree ptr_ref = TREE_OPERAND (ref, 0);
- tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
- tree init = initial_condition_in_loop_num (access_fn, loop->num);
- tree base_address = NULL_TREE, evolution, step = NULL_TREE;
- struct ptr_info_def *ptr_info = NULL;
-
- if (TREE_CODE (ptr_ref) == SSA_NAME)
- ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
-
- STRIP_NOPS (init);
- if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nBad access function of ptr: ");
- print_generic_expr (dump_file, ref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nAccess function of ptr: ");
- print_generic_expr (dump_file, access_fn, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
-
- if (!expr_invariant_in_loop_p (loop, init))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
- }
- else
- {
- base_address = init;
- evolution = evolution_part_in_loop_num (access_fn, loop->num);
- if (evolution != chrec_dont_know)
- {
- if (!evolution)
- step = ssize_int (0);
- else
- {
- if (TREE_CODE (evolution) == INTEGER_CST)
- step = fold_convert (ssizetype, evolution);
- else
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nnon constant step for ptr access.\n");
- }
- }
- else
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nunknown evolution of ptr.\n");
- }
- return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address,
- NULL_TREE, step, NULL_TREE, NULL_TREE,
- ptr_info, POINTER_REF_TYPE);
-}
-
-/* For a data reference REF contained in the statement STMT, initialize
- a DATA_REFERENCE structure, and return it. */
-
-struct data_reference *
-init_data_ref (tree stmt,
- tree ref,
- tree base,
- tree access_fn,
- bool is_read,
- tree base_address,
- tree init_offset,
- tree step,
- tree misalign,
- tree memtag,
- struct ptr_info_def *ptr_info,
- enum data_ref_type type)
-{
- struct data_reference *res;
- VEC(tree,heap) *acc_fns;
-
- 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 = XNEW (struct data_reference);
-
- DR_STMT (res) = stmt;
- DR_REF (res) = ref;
- DR_BASE_OBJECT (res) = base;
- DR_TYPE (res) = type;
- acc_fns = VEC_alloc (tree, heap, 3);
- DR_SET_ACCESS_FNS (res, acc_fns);
- VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
- DR_IS_READ (res) = is_read;
- DR_BASE_ADDRESS (res) = base_address;
- DR_OFFSET (res) = init_offset;
- DR_INIT (res) = NULL_TREE;
- DR_STEP (res) = step;
- DR_OFFSET_MISALIGNMENT (res) = misalign;
- DR_MEMTAG (res) = memtag;
- DR_PTR_INFO (res) = ptr_info;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-
- return res;
-}
-
-/* Function strip_conversions
-
- Strip conversions that don't narrow the mode. */
-
-static tree
-strip_conversion (tree expr)
-{
- tree to, ti, oprnd0;
-
- while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
- {
- to = TREE_TYPE (expr);
- oprnd0 = TREE_OPERAND (expr, 0);
- ti = TREE_TYPE (oprnd0);
-
- if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
- return NULL_TREE;
- if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
- return NULL_TREE;
-
- expr = oprnd0;
- }
- return expr;
-}
-
-
-/* Function analyze_offset_expr
-
- Given an offset expression EXPR received from get_inner_reference, analyze
- it and create an expression for INITIAL_OFFSET by substituting the variables
- of EXPR with initial_condition of the corresponding access_fn in the loop.
- E.g.,
- for i
- for (j = 3; j < N; j++)
- a[j].b[i][j] = 0;
-
- For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
- substituted, since its access_fn in the inner loop is i. 'j' will be
- substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
- C` = 3 * C_j + C.
-
- Compute MISALIGN (the misalignment of the data reference initial access from
- its base). Misalignment can be calculated only if all the variables can be
- substituted with constants, otherwise, we record maximum possible alignment
- in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
- will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
- recorded in ALIGNED_TO.
-
- STEP is an evolution of the data reference in this loop in bytes.
- In the above example, STEP is C_j.
-
- Return FALSE, if the analysis fails, e.g., there is no access_fn for a
- variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
- and STEP) are NULL_TREEs. Otherwise, return TRUE.
-
-*/
-
-static bool
-analyze_offset_expr (tree expr,
- struct loop *loop,
- tree *initial_offset,
- tree *misalign,
- tree *aligned_to,
- tree *step)
-{
- tree oprnd0;
- tree oprnd1;
- tree left_offset = ssize_int (0);
- tree right_offset = ssize_int (0);
- tree left_misalign = ssize_int (0);
- tree right_misalign = ssize_int (0);
- tree left_step = ssize_int (0);
- tree right_step = ssize_int (0);
- enum tree_code code;
- tree init, evolution;
- tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
-
- *step = NULL_TREE;
- *misalign = NULL_TREE;
- *aligned_to = NULL_TREE;
- *initial_offset = NULL_TREE;
-
- /* Strip conversions that don't narrow the mode. */
- expr = strip_conversion (expr);
- if (!expr)
- return false;
-
- /* Stop conditions:
- 1. Constant. */
- if (TREE_CODE (expr) == INTEGER_CST)
- {
- *initial_offset = fold_convert (ssizetype, expr);
- *misalign = fold_convert (ssizetype, expr);
- *step = ssize_int (0);
- return true;
- }
-
- /* 2. Variable. Try to substitute with initial_condition of the corresponding
- access_fn in the current loop. */
- if (SSA_VAR_P (expr))
- {
- tree access_fn = analyze_scalar_evolution (loop, expr);
-
- if (access_fn == chrec_dont_know)
- /* No access_fn. */
- return false;
-
- init = initial_condition_in_loop_num (access_fn, loop->num);
- if (!expr_invariant_in_loop_p (loop, init))
- /* Not enough information: may be not loop invariant.
- E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
- initial_condition is D, but it depends on i - loop's induction
- variable. */
- return false;
-
- evolution = evolution_part_in_loop_num (access_fn, loop->num);
- if (evolution && TREE_CODE (evolution) != INTEGER_CST)
- /* Evolution is not constant. */
- return false;
-
- if (TREE_CODE (init) == INTEGER_CST)
- *misalign = fold_convert (ssizetype, init);
- else
- /* Not constant, misalignment cannot be calculated. */
- *misalign = NULL_TREE;
-
- *initial_offset = fold_convert (ssizetype, init);
-
- *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
- return true;
- }
-
- /* Recursive computation. */
- if (!BINARY_CLASS_P (expr))
- {
- /* We expect to get binary expressions (PLUS/MINUS and MULT). */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nNot binary expression ");
- print_generic_expr (dump_file, expr, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return false;
- }
- oprnd0 = TREE_OPERAND (expr, 0);
- oprnd1 = TREE_OPERAND (expr, 1);
-
- if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
- &left_aligned_to, &left_step)
- || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
- &right_aligned_to, &right_step))
- return false;
-
- /* The type of the operation: plus, minus or mult. */
- code = TREE_CODE (expr);
- switch (code)
- {
- case MULT_EXPR:
- if (TREE_CODE (right_offset) != INTEGER_CST)
- /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
- sized types.
- FORNOW: We don't support such cases. */
- return false;
-
- /* Strip conversions that don't narrow the mode. */
- left_offset = strip_conversion (left_offset);
- if (!left_offset)
- return false;
- /* Misalignment computation. */
- if (SSA_VAR_P (left_offset))
- {
- /* If the left side contains variables that can't be substituted with
- constants, the misalignment is unknown. However, if the right side
- is a multiple of some alignment, we know that the expression is
- aligned to it. Therefore, we record such maximum possible value.
- */
- *misalign = NULL_TREE;
- *aligned_to = ssize_int (highest_pow2_factor (right_offset));
- }
- else
- {
- /* The left operand was successfully substituted with constant. */
- if (left_misalign)
- {
- /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
- NULL_TREE. */
- *misalign = size_binop (code, left_misalign, right_misalign);
- if (left_aligned_to && right_aligned_to)
- *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
- right_aligned_to);
- else
- *aligned_to = left_aligned_to ?
- left_aligned_to : right_aligned_to;
- }
- else
- *misalign = NULL_TREE;
- }
-
- /* Step calculation. */
- /* Multiply the step by the right operand. */
- *step = size_binop (MULT_EXPR, left_step, right_offset);
- break;
-
- case PLUS_EXPR:
- case MINUS_EXPR:
- /* Combine the recursive calculations for step and misalignment. */
- *step = size_binop (code, left_step, right_step);
-
- /* Unknown alignment. */
- if ((!left_misalign && !left_aligned_to)
- || (!right_misalign && !right_aligned_to))
- {
- *misalign = NULL_TREE;
- *aligned_to = NULL_TREE;
- break;
- }
-
- if (left_misalign && right_misalign)
- *misalign = size_binop (code, left_misalign, right_misalign);
- else
- *misalign = left_misalign ? left_misalign : right_misalign;
-
- if (left_aligned_to && right_aligned_to)
- *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
- else
- *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
-
- break;
-
- default:
- gcc_unreachable ();
- }
-
- /* Compute offset. */
- *initial_offset = fold_convert (ssizetype,
- fold_build2 (code, TREE_TYPE (left_offset),
- left_offset,
- right_offset));
- return true;
-}
-
-/* Function address_analysis
-
- Return the BASE of the address expression EXPR.
- Also compute the OFFSET from BASE, MISALIGN and STEP.
-
- Input:
- EXPR - the address expression that is being analyzed
- STMT - the statement that contains EXPR or its original memory reference
- IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
- DR - data_reference struct for the original memory reference
-
- Output:
- BASE (returned value) - the base of the data reference EXPR.
- INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
- MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
- computation is impossible
- ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
- calculated (doesn't depend on variables)
- STEP - evolution of EXPR in the loop
-
- If something unexpected is encountered (an unsupported form of data-ref),
- then NULL_TREE is returned.
- */
-
-static tree
-address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
- tree *offset, tree *misalign, tree *aligned_to, tree *step)
-{
- tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
- tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
- tree dummy, address_aligned_to = NULL_TREE;
- struct ptr_info_def *dummy1;
- subvar_t dummy2;
-
- switch (TREE_CODE (expr))
- {
- case PLUS_EXPR:
- case MINUS_EXPR:
- /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
- oprnd0 = TREE_OPERAND (expr, 0);
- oprnd1 = TREE_OPERAND (expr, 1);
-
- STRIP_NOPS (oprnd0);
- STRIP_NOPS (oprnd1);
-
- /* Recursively try to find the base of the address contained in EXPR.
- For offset, the returned base will be NULL. */
- base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
- &address_misalign, &address_aligned_to,
- step);
-
- base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
- &address_misalign, &address_aligned_to,
- step);
-
- /* We support cases where only one of the operands contains an
- address. */
- if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file,
- "\neither more than one address or no addresses in expr ");
- print_generic_expr (dump_file, expr, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
-
- /* To revert STRIP_NOPS. */
- oprnd0 = TREE_OPERAND (expr, 0);
- oprnd1 = TREE_OPERAND (expr, 1);
-
- offset_expr = base_addr0 ?
- fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
-
- /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
- a number, we can add it to the misalignment value calculated for base,
- otherwise, misalignment is NULL. */
- if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
- {
- *misalign = size_binop (TREE_CODE (expr), address_misalign,
- offset_expr);
- *aligned_to = address_aligned_to;
- }
- else
- {
- *misalign = NULL_TREE;
- *aligned_to = NULL_TREE;
- }
-
- /* Combine offset (from EXPR {base + offset}) with the offset calculated
- for base. */
- *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
- return base_addr0 ? base_addr0 : base_addr1;
-
- case ADDR_EXPR:
- base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
- &dr, offset, misalign, aligned_to, step,
- &dummy, &dummy1, &dummy2);
- return base_address;
-
- case SSA_NAME:
- if (!POINTER_TYPE_P (TREE_TYPE (expr)))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nnot pointer SSA_NAME ");
- print_generic_expr (dump_file, expr, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
- *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
- *misalign = ssize_int (0);
- *offset = ssize_int (0);
- *step = ssize_int (0);
- return expr;
-
- default:
- return NULL_TREE;
- }
-}
-
-
-/* Function object_analysis
-
- Create a data-reference structure DR for MEMREF.
- Return the BASE of the data reference MEMREF if the analysis is possible.
- Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
- E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
- 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
- instantiated with initial_conditions of access_functions of variables,
- and STEP is the evolution of the DR_REF in this loop.
-
- Function get_inner_reference is used for the above in case of ARRAY_REF and
- COMPONENT_REF.
-
- The structure of the function is as follows:
- Part 1:
- Case 1. For handled_component_p refs
- 1.1 build data-reference structure for MEMREF
- 1.2 call get_inner_reference
- 1.2.1 analyze offset expr received from get_inner_reference
- (fall through with BASE)
- Case 2. For declarations
- 2.1 set MEMTAG
- Case 3. For INDIRECT_REFs
- 3.1 build data-reference structure for MEMREF
- 3.2 analyze evolution and initial condition of MEMREF
- 3.3 set data-reference structure for MEMREF
- 3.4 call address_analysis to analyze INIT of the access function
- 3.5 extract memory tag
-
- Part 2:
- Combine the results of object and address analysis to calculate
- INITIAL_OFFSET, STEP and misalignment info.
-
- Input:
- MEMREF - the memory reference that is being analyzed
- STMT - the statement that contains MEMREF
- IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
-
- Output:
- BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
- E.g, if MEMREF is a.b[k].c[i][j] the returned
- base is &a.
- DR - data_reference struct for MEMREF
- INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
- MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
- ALIGNMENT or NULL_TREE if the computation is impossible
- ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
- calculated (doesn't depend on variables)
- STEP - evolution of the DR_REF in the loop
- MEMTAG - memory tag for aliasing purposes
- PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
- SUBVARS - Sub-variables of the variable
-
- If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
- but DR can be created anyway.
-
-*/
-
-static tree
-object_analysis (tree memref, tree stmt, bool is_read,
- struct data_reference **dr, tree *offset, tree *misalign,
- tree *aligned_to, tree *step, tree *memtag,
- struct ptr_info_def **ptr_info, subvar_t *subvars)
-{
- tree base = NULL_TREE, base_address = NULL_TREE;
- tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
- tree object_step = ssize_int (0), address_step = ssize_int (0);
- tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
- HOST_WIDE_INT pbitsize, pbitpos;
- tree poffset, bit_pos_in_bytes;
- enum machine_mode pmode;
- int punsignedp, pvolatilep;
- tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
- struct loop *loop = loop_containing_stmt (stmt);
- struct data_reference *ptr_dr = NULL;
- tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
- tree comp_ref = NULL_TREE;
-
- *ptr_info = NULL;
-
- /* Part 1: */
- /* Case 1. handled_component_p refs. */
- if (handled_component_p (memref))
- {
- /* 1.1 build data-reference structure for MEMREF. */
- if (!(*dr))
- {
- if (TREE_CODE (memref) == ARRAY_REF)
- *dr = analyze_array (stmt, memref, is_read);
- else if (TREE_CODE (memref) == COMPONENT_REF)
- comp_ref = memref;
- else
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\ndata-ref of unsupported type ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
- }
-
- /* 1.2 call get_inner_reference. */
- /* Find the base and the offset from it. */
- base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
- &pmode, &punsignedp, &pvolatilep, false);
- if (!base)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nfailed to get inner ref for ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
-
- /* 1.2.1 analyze offset expr received from get_inner_reference. */
- if (poffset
- && !analyze_offset_expr (poffset, loop, &object_offset,
- &object_misalign, &object_aligned_to,
- &object_step))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nfailed to compute offset or step for ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
-
- /* Add bit position to OFFSET and MISALIGN. */
-
- bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
- /* Check that there is no remainder in bits. */
- if (pbitpos%BITS_PER_UNIT)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nbit offset alignment.\n");
- return NULL_TREE;
- }
- object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
- if (object_misalign)
- object_misalign = size_binop (PLUS_EXPR, object_misalign,
- bit_pos_in_bytes);
-
- memref = base; /* To continue analysis of BASE. */
- /* fall through */
- }
-
- /* Part 1: Case 2. Declarations. */
- if (DECL_P (memref))
- {
- /* We expect to get a decl only if we already have a DR, or with
- COMPONENT_REFs of type 'a[i].b'. */
- if (!(*dr))
- {
- if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
- {
- *dr = analyze_array (stmt, TREE_OPERAND (comp_ref, 0), is_read);
- if (DR_NUM_DIMENSIONS (*dr) != 1)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\n multidimensional component ref ");
- print_generic_expr (dump_file, comp_ref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
- }
- else
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nunhandled decl ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
- }
-
- /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
- the object in BASE_OBJECT field if we can prove that this is O.K.,
- i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
- (e.g., if the object is an array base 'a', where 'a[N]', we must prove
- that every access with 'p' (the original INDIRECT_REF based on '&a')
- in the loop is within the array boundaries - from a[0] to a[N-1]).
- Otherwise, our alias analysis can be incorrect.
- Even if an access function based on BASE_OBJECT can't be build, update
- BASE_OBJECT field to enable us to prove that two data-refs are
- different (without access function, distance analysis is impossible).
- */
- if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
- *subvars = get_subvars_for_var (memref);
- base_address = build_fold_addr_expr (memref);
- /* 2.1 set MEMTAG. */
- *memtag = memref;
- }
-
- /* Part 1: Case 3. INDIRECT_REFs. */
- else if (TREE_CODE (memref) == INDIRECT_REF)
- {
- tree ptr_ref = TREE_OPERAND (memref, 0);
- if (TREE_CODE (ptr_ref) == SSA_NAME)
- *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
-
- /* 3.1 build data-reference structure for MEMREF. */
- ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
- if (!ptr_dr)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nfailed to create dr for ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
-
- /* 3.2 analyze evolution and initial condition of MEMREF. */
- ptr_step = DR_STEP (ptr_dr);
- ptr_init = DR_BASE_ADDRESS (ptr_dr);
- if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
- {
- *dr = (*dr) ? *dr : ptr_dr;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nbad pointer access ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
-
- if (integer_zerop (ptr_step) && !(*dr))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nptr is loop invariant.\n");
- *dr = ptr_dr;
- return NULL_TREE;
-
- /* If there exists DR for MEMREF, we are analyzing the base of
- handled component (PTR_INIT), which not necessary has evolution in
- the loop. */
- }
- object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
-
- /* 3.3 set data-reference structure for MEMREF. */
- if (!*dr)
- *dr = ptr_dr;
-
- /* 3.4 call address_analysis to analyze INIT of the access
- function. */
- base_address = address_analysis (ptr_init, stmt, is_read, *dr,
- &address_offset, &address_misalign,
- &address_aligned_to, &address_step);
- if (!base_address)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nfailed to analyze address ");
- print_generic_expr (dump_file, ptr_init, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
-
- /* 3.5 extract memory tag. */
- switch (TREE_CODE (base_address))
- {
- case SSA_NAME:
- *memtag = get_var_ann (SSA_NAME_VAR (base_address))->symbol_mem_tag;
- if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
- *memtag = get_var_ann (
- SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->symbol_mem_tag;
- break;
- case ADDR_EXPR:
- *memtag = TREE_OPERAND (base_address, 0);
- break;
- default:
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nno memtag for ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- *memtag = NULL_TREE;
- break;
- }
- }
-
- if (!base_address)
- {
- /* MEMREF cannot be analyzed. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\ndata-ref of unsupported type ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
-
- if (comp_ref)
- DR_REF (*dr) = comp_ref;
-
- if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
- *subvars = get_subvars_for_var (*memtag);
-
- /* Part 2: Combine the results of object and address analysis to calculate
- INITIAL_OFFSET, STEP and misalignment info. */
- *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
-
- if ((!object_misalign && !object_aligned_to)
- || (!address_misalign && !address_aligned_to))
- {
- *misalign = NULL_TREE;
- *aligned_to = NULL_TREE;
- }
- else
- {
- if (object_misalign && address_misalign)
- *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
- else
- *misalign = object_misalign ? object_misalign : address_misalign;
- if (object_aligned_to && address_aligned_to)
- *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
- address_aligned_to);
- else
- *aligned_to = object_aligned_to ?
- object_aligned_to : address_aligned_to;
- }
- *step = size_binop (PLUS_EXPR, object_step, address_step);
-
- return base_address;
-}
-
-/* Function analyze_offset.
-
- Extract INVARIANT and CONSTANT parts from OFFSET.
-
-*/
-static bool
-analyze_offset (tree offset, tree *invariant, tree *constant)
-{
- tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
- enum tree_code code = TREE_CODE (offset);
-
- *invariant = NULL_TREE;
- *constant = NULL_TREE;
-
- /* Not PLUS/MINUS expression - recursion stop condition. */
- if (code != PLUS_EXPR && code != MINUS_EXPR)
- {
- if (TREE_CODE (offset) == INTEGER_CST)
- *constant = offset;
- else
- *invariant = offset;
- return true;
- }
-
- op0 = TREE_OPERAND (offset, 0);
- op1 = TREE_OPERAND (offset, 1);
-
- /* Recursive call with the operands. */
- if (!analyze_offset (op0, &invariant_0, &constant_0)
- || !analyze_offset (op1, &invariant_1, &constant_1))
- return false;
-
- /* Combine the results. Add negation to the subtrahend in case of
- subtraction. */
- if (constant_0 && constant_1)
- return false;
- *constant = constant_0 ? constant_0 : constant_1;
- if (code == MINUS_EXPR && constant_1)
- *constant = fold_build1 (NEGATE_EXPR, TREE_TYPE (*constant), *constant);
-
- if (invariant_0 && invariant_1)
- *invariant =
- fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
- else
- {
- *invariant = invariant_0 ? invariant_0 : invariant_1;
- if (code == MINUS_EXPR && invariant_1)
- *invariant =
- fold_build1 (NEGATE_EXPR, TREE_TYPE (*invariant), *invariant);
- }
- return true;
-}
-
-/* Free the memory used by the data reference DR. */
-
-static void
-free_data_ref (data_reference_p dr)
-{
- DR_FREE_ACCESS_FNS (dr);
- free (dr);
-}
-
-/* Function create_data_ref.
-
- Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
- DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
- DR_MEMTAG, and DR_POINTSTO_INFO fields.
-
- Input:
- MEMREF - the memory reference that is being analyzed
- STMT - the statement that contains MEMREF
- IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
-
- Output:
- DR (returned value) - data_reference struct for MEMREF
-*/
-
-static struct data_reference *
-create_data_ref (tree memref, tree stmt, bool is_read)
-{
- struct data_reference *dr = NULL;
- tree base_address, offset, step, misalign, memtag;
- struct loop *loop = loop_containing_stmt (stmt);
- tree invariant = NULL_TREE, constant = NULL_TREE;
- tree type_size, init_cond;
- struct ptr_info_def *ptr_info;
- subvar_t subvars = NULL;
- tree aligned_to, type = NULL_TREE, orig_offset;
-
- if (!memref)
- return NULL;
-
- base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
- &misalign, &aligned_to, &step, &memtag,
- &ptr_info, &subvars);
- if (!dr || !base_address)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL;
- }
-
- DR_BASE_ADDRESS (dr) = base_address;
- DR_OFFSET (dr) = offset;
- DR_INIT (dr) = ssize_int (0);
- DR_STEP (dr) = step;
- DR_OFFSET_MISALIGNMENT (dr) = misalign;
- DR_ALIGNED_TO (dr) = aligned_to;
- DR_MEMTAG (dr) = memtag;
- DR_PTR_INFO (dr) = ptr_info;
- DR_SUBVARS (dr) = subvars;
-
- type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
-
- /* Extract CONSTANT and INVARIANT from OFFSET. */
- /* Remove cast from OFFSET and restore it for INVARIANT part. */
- orig_offset = offset;
- STRIP_NOPS (offset);
- if (offset != orig_offset)
- type = TREE_TYPE (orig_offset);
- if (!analyze_offset (offset, &invariant, &constant))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\ncreate_data_ref: failed to analyze dr's");
- fprintf (dump_file, " offset for ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL;
- }
- if (type && invariant)
- invariant = fold_convert (type, invariant);
-
- /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
- of DR. */
- if (constant)
- {
- DR_INIT (dr) = fold_convert (ssizetype, constant);
- init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
- constant, type_size);
- }
- else
- DR_INIT (dr) = init_cond = ssize_int (0);
-
- if (invariant)
- DR_OFFSET (dr) = invariant;
- else
- DR_OFFSET (dr) = ssize_int (0);
-
- /* Change the access function for INIDIRECT_REFs, according to
- DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is
- an expression that can contain loop invariant expressions and constants.
- We put the constant part in the initial condition of the access function
- (for data dependence tests), and in DR_INIT of the data-ref. The loop
- invariant part is put in DR_OFFSET.
- The evolution part of the access function is STEP calculated in
- object_analysis divided by the size of data type.
- */
- if (!DR_BASE_OBJECT (dr)
- || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
- {
- tree access_fn;
- tree new_step;
-
- /* Update access function. */
- access_fn = DR_ACCESS_FN (dr, 0);
- if (automatically_generated_chrec_p (access_fn))
- {
- free_data_ref (dr);
- return NULL;
- }
-
- new_step = size_binop (TRUNC_DIV_EXPR,
- fold_convert (ssizetype, step), type_size);
-
- init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
- new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
- if (automatically_generated_chrec_p (init_cond)
- || automatically_generated_chrec_p (new_step))
- {
- free_data_ref (dr);
- return NULL;
- }
- access_fn = chrec_replace_initial_condition (access_fn, init_cond);
- access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
-
- VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- struct ptr_info_def *pi = DR_PTR_INFO (dr);
-
- fprintf (dump_file, "\nCreated dr for ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n\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\tbase_object: ");
- print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
- fprintf (dump_file, "\n\tstep: ");
- print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
- fprintf (dump_file, "B\n\tmisalignment from base: ");
- print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
- if (DR_OFFSET_MISALIGNMENT (dr))
- fprintf (dump_file, "B");
- if (DR_ALIGNED_TO (dr))
- {
- fprintf (dump_file, "\n\taligned to: ");
- print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
- }
- fprintf (dump_file, "\n\tmemtag: ");
- print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
- fprintf (dump_file, "\n");
- if (pi && pi->name_mem_tag)
- {
- fprintf (dump_file, "\n\tnametag: ");
- print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- }
- return dr;
-}
-
-
-/* Returns true when all the functions of a tree_vec CHREC are the
- same. */
-
-static bool
-all_chrecs_equal_p (tree chrec)
-{
- int j;
-
- for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
- if (!eq_evolutions_p (TREE_VEC_ELT (chrec, j),
- TREE_VEC_ELT (chrec, j + 1)))
- return false;
-
- return true;
-}
-
-/* Determine for each subscript in the data dependence relation DDR
- the distance. */
-
-static void
-compute_subscript_distance (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);
-
- if (TREE_CODE (conflicts_a) == TREE_VEC)
- {
- if (!all_chrecs_equal_p (conflicts_a))
- {
- SUB_DISTANCE (subscript) = chrec_dont_know;
- return;
- }
- else
- conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
- }
-
- if (TREE_CODE (conflicts_b) == TREE_VEC)
- {
- if (!all_chrecs_equal_p (conflicts_b))
- {
- SUB_DISTANCE (subscript) = chrec_dont_know;
- return;
- }
- else
- conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
- }
-
- conflicts_b = chrec_convert (integer_type_node, conflicts_b,
- NULL_TREE);
- conflicts_a = chrec_convert (integer_type_node, conflicts_a,
- NULL_TREE);
- 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 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. */
-
-static struct data_dependence_relation *
-initialize_data_dependence_relation (struct data_reference *a,
- struct data_reference *b,
- VEC (loop_p, heap) *loop_nest)
-{
- struct data_dependence_relation *res;
- bool differ_p, known_dependence;
- unsigned int i;
-
- res = XNEW (struct data_dependence_relation);
- DDR_A (res) = a;
- DDR_B (res) = b;
- DDR_LOOP_NEST (res) = NULL;
-
- if (a == NULL || b == NULL)
- {
- DDR_ARE_DEPENDENT (res) = chrec_dont_know;
- return res;
- }
-
- /* When A and B are arrays and their dimensions differ, we directly
- initialize the relation to "there is no dependence": chrec_known. */
- if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
- && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
- {
- DDR_ARE_DEPENDENT (res) = chrec_known;
- return res;
- }
-
- if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
- known_dependence = base_addr_differ_p (a, b, &differ_p);
- else
- known_dependence = base_object_differ_p (a, b, &differ_p);
-
- if (!known_dependence)
- {
- /* Can't determine whether the data-refs access the same memory
- region. */
- DDR_ARE_DEPENDENT (res) = chrec_dont_know;
- return res;
- }
-
- if (differ_p)
- {
- DDR_ARE_DEPENDENT (res) = chrec_known;
- return res;
- }
-
- DDR_AFFINE_P (res) = true;
- DDR_ARE_DEPENDENT (res) = NULL_TREE;
- DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
- DDR_LOOP_NEST (res) = loop_nest;
- DDR_DIR_VECTS (res) = NULL;
- DDR_DIST_VECTS (res) = NULL;
-
- for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
- {
- struct subscript *subscript;
-
- subscript = XNEW (struct subscript);
- SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
- SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
- SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
- SUB_DISTANCE (subscript) = chrec_dont_know;
- VEC_safe_push (subscript_p, heap, 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)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(dependence classified: ");
- print_generic_expr (dump_file, chrec, 0);
- fprintf (dump_file, ")\n");
- }
-
- DDR_ARE_DEPENDENT (ddr) = chrec;
- VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
-}
-
-/* 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 (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 *last_conflicts)
-{
- tree difference;
- dependence_stats.num_ziv++;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_ziv_subscript \n");
-
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- 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;
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_ziv_dependent++;
- }
- else
- {
- /* The accesses do not overlap. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *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 = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_ziv_unimplemented++;
- break;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Get the real or estimated number of iterations for LOOPNUM, whichever is
- available. Return the number of iterations as a tree, or NULL_TREE if
- we don't know. */
-
-static tree
-get_number_of_iters_for_loop (int loopnum)
-{
- tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
-
- if (TREE_CODE (numiter) != INTEGER_CST)
- numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
- if (chrec_contains_undetermined (numiter))
- return NULL_TREE;
- return numiter;
-}
-
-/* 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,
- tree *last_conflicts)
-{
- bool value0, value1, value2;
- tree difference;
-
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- difference = chrec_fold_minus
- (integer_type_node, initial_condition (chrec_b), chrec_a);
-
- 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 = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- return;
- }
- else
- {
- if (value0 == false)
- {
- if (!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 = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *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))
- {
- tree numiter;
- int loopnum = CHREC_VARIABLE (chrec_b);
-
- *overlaps_a = integer_zero_node;
- *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
- fold_build1 (ABS_EXPR,
- integer_type_node,
- difference),
- CHREC_RIGHT (chrec_b));
- *last_conflicts = integer_one_node;
-
-
- /* Perform weak-zero siv test to see if overlap is
- outside the loop bounds. */
- numiter = get_number_of_iters_for_loop (loopnum);
-
- if (numiter != NULL_TREE
- && TREE_CODE (*overlaps_b) == INTEGER_CST
- && tree_int_cst_lt (numiter, *overlaps_b))
- {
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *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 = chrec_known;
- *overlaps_b = chrec_known;
- *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 = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- dependence_stats.num_siv_independent++;
- return;
- }
- }
- }
- else
- {
- if (!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 = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *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))
- {
- tree numiter;
- int loopnum = CHREC_VARIABLE (chrec_b);
-
- *overlaps_a = integer_zero_node;
- *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
- integer_type_node, difference,
- CHREC_RIGHT (chrec_b));
- *last_conflicts = integer_one_node;
-
- /* Perform weak-zero siv test to see if overlap is
- outside the loop bounds. */
- numiter = get_number_of_iters_for_loop (loopnum);
-
- if (numiter != NULL_TREE
- && TREE_CODE (*overlaps_b) == INTEGER_CST
- && tree_int_cst_lt (numiter, *overlaps_b))
- {
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *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 = chrec_known;
- *overlaps_b = chrec_known;
- *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 = chrec_known;
- *overlaps_b = chrec_known;
- *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 int
-initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
-{
- gcc_assert (chrec);
-
- if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
- return int_cst_value (chrec);
-
- A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
- return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
-}
-
-#define FLOOR_DIV(x,y) ((x) / (y))
-
-/* Solves the special case of the Diophantine equation:
- | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
-
- Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
- number of iterations that loops X and Y run. The overlaps will be
- constructed as evolutions in dimension DIM. */
-
-static void
-compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
- tree *overlaps_a, tree *overlaps_b,
- tree *last_conflicts, int dim)
-{
- if (((step_a > 0 && step_b > 0)
- || (step_a < 0 && step_b < 0)))
- {
- int step_overlaps_a, step_overlaps_b;
- int gcd_steps_a_b, last_conflict, tau2;
-
- gcd_steps_a_b = gcd (step_a, step_b);
- step_overlaps_a = step_b / gcd_steps_a_b;
- step_overlaps_b = step_a / gcd_steps_a_b;
-
- tau2 = FLOOR_DIV (niter, step_overlaps_a);
- tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
- last_conflict = tau2;
-
- *overlaps_a = build_polynomial_chrec
- (dim, integer_zero_node,
- build_int_cst (NULL_TREE, step_overlaps_a));
- *overlaps_b = build_polynomial_chrec
- (dim, integer_zero_node,
- build_int_cst (NULL_TREE, step_overlaps_b));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
- }
-
- else
- {
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = integer_zero_node;
- }
-}
-
-
-/* Solves the special case of a Diophantine equation where CHREC_A is
- an affine bivariate function, and CHREC_B is an affine univariate
- function. For example,
-
- | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
-
- has the following overlapping functions:
-
- | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
- | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
- | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
-
- FORNOW: This is a specialized implementation for a case occurring in
- a common benchmark. Implement the general algorithm. */
-
-static void
-compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
- tree *overlaps_a, tree *overlaps_b,
- tree *last_conflicts)
-{
- bool xz_p, yz_p, xyz_p;
- int step_x, step_y, step_z;
- int niter_x, niter_y, niter_z, niter;
- tree numiter_x, numiter_y, numiter_z;
- tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
- tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
- tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
-
- step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
- step_y = int_cst_value (CHREC_RIGHT (chrec_a));
- step_z = int_cst_value (CHREC_RIGHT (chrec_b));
-
- numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
- numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
- numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
-
- if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
- || numiter_z == NULL_TREE)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
-
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- return;
- }
-
- niter_x = int_cst_value (numiter_x);
- niter_y = int_cst_value (numiter_y);
- niter_z = int_cst_value (numiter_z);
-
- niter = MIN (niter_x, niter_z);
- compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
- &overlaps_a_xz,
- &overlaps_b_xz,
- &last_conflicts_xz, 1);
- niter = MIN (niter_y, niter_z);
- compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
- &overlaps_a_yz,
- &overlaps_b_yz,
- &last_conflicts_yz, 2);
- niter = MIN (niter_x, niter_z);
- niter = MIN (niter_y, niter);
- compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
- &overlaps_a_xyz,
- &overlaps_b_xyz,
- &last_conflicts_xyz, 3);
-
- xz_p = !integer_zerop (last_conflicts_xz);
- yz_p = !integer_zerop (last_conflicts_yz);
- xyz_p = !integer_zerop (last_conflicts_xyz);
-
- if (xz_p || yz_p || xyz_p)
- {
- *overlaps_a = make_tree_vec (2);
- TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
- TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
- *overlaps_b = integer_zero_node;
- if (xz_p)
- {
- tree t0 = chrec_convert (integer_type_node,
- TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
- tree t1 = chrec_convert (integer_type_node, overlaps_a_xz,
- NULL_TREE);
- tree t2 = chrec_convert (integer_type_node, *overlaps_b,
- NULL_TREE);
- tree t3 = chrec_convert (integer_type_node, overlaps_b_xz,
- NULL_TREE);
-
- TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
- t0, t1);
- *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
- *last_conflicts = last_conflicts_xz;
- }
- if (yz_p)
- {
- tree t0 = chrec_convert (integer_type_node,
- TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
- tree t1 = chrec_convert (integer_type_node, overlaps_a_yz, NULL_TREE);
- tree t2 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
- tree t3 = chrec_convert (integer_type_node, overlaps_b_yz, NULL_TREE);
-
- TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
- t0, t1);
- *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
- *last_conflicts = last_conflicts_yz;
- }
- if (xyz_p)
- {
- tree t0 = chrec_convert (integer_type_node,
- TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
- tree t1 = chrec_convert (integer_type_node, overlaps_a_xyz,
- NULL_TREE);
- tree t2 = chrec_convert (integer_type_node,
- TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
- tree t3 = chrec_convert (integer_type_node, overlaps_a_xyz,
- NULL_TREE);
- tree t4 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
- tree t5 = chrec_convert (integer_type_node, overlaps_b_xyz,
- NULL_TREE);
-
- TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
- t0, t1);
- TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
- t2, t3);
- *overlaps_b = chrec_fold_plus (integer_type_node, t4, t5);
- *last_conflicts = last_conflicts_xyz;
- }
- }
- else
- {
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = integer_zero_node;
- }
-}
-
-/* Determines the overlapping elements due to accesses CHREC_A and
- CHREC_B, that are affine functions. This function cannot handle
- symbolic evolution functions, ie. when initial conditions are
- parameters, because it uses lambda matrices of integers. */
-
-static void
-analyze_subscript_affine_affine (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
- tree *last_conflicts)
-{
- unsigned nb_vars_a, nb_vars_b, dim;
- int init_a, init_b, gamma, gcd_alpha_beta;
- int tau1, tau2;
- lambda_matrix A, U, S;
-
- if (eq_evolutions_p (chrec_a, chrec_b))
- {
- /* The accessed index overlaps for each iteration in the
- loop. */
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = chrec_dont_know;
- return;
- }
- 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,
- i.e. 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. */
-
- nb_vars_a = nb_vars_in_chrec (chrec_a);
- nb_vars_b = nb_vars_in_chrec (chrec_b);
-
- dim = nb_vars_a + nb_vars_b;
- U = lambda_matrix_new (dim, dim);
- A = lambda_matrix_new (dim, 1);
- S = lambda_matrix_new (dim, 1);
-
- init_a = initialize_matrix_A (A, chrec_a, 0, 1);
- init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
- gamma = init_b - init_a;
-
- /* Don't do all the hard work of solving the Diophantine equation
- when we already know the solution: for example,
- | {3, +, 1}_1
- | {3, +, 4}_2
- | gamma = 3 - 3 = 0.
- Then the first overlap occurs during the first iterations:
- | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
- */
- if (gamma == 0)
- {
- if (nb_vars_a == 1 && nb_vars_b == 1)
- {
- int step_a, step_b;
- int niter, niter_a, niter_b;
- tree numiter_a, numiter_b;
-
- numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
- numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
- if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- goto end_analyze_subs_aa;
- }
-
- niter_a = int_cst_value (numiter_a);
- niter_b = int_cst_value (numiter_b);
- niter = MIN (niter_a, niter_b);
-
- step_a = int_cst_value (CHREC_RIGHT (chrec_a));
- step_b = int_cst_value (CHREC_RIGHT (chrec_b));
-
- compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
- overlaps_a, overlaps_b,
- last_conflicts, 1);
- }
-
- else if (nb_vars_a == 2 && nb_vars_b == 1)
- compute_overlap_steps_for_affine_1_2
- (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
-
- else if (nb_vars_a == 1 && nb_vars_b == 2)
- compute_overlap_steps_for_affine_1_2
- (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
-
- else
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: too many variables.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
- goto end_analyze_subs_aa;
- }
-
- /* U.A = S */
- lambda_matrix_right_hermite (A, dim, 1, S, U);
-
- if (S[0][0] < 0)
- {
- S[0][0] *= -1;
- lambda_matrix_row_negate (U, dim, 0);
- }
- gcd_alpha_beta = S[0][0];
-
- /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
- but that is a quite strange case. Instead of ICEing, answer
- don't know. */
- if (gcd_alpha_beta == 0)
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- goto end_analyze_subs_aa;
- }
-
- /* The classic "gcd-test". */
- if (!int_divides_p (gcd_alpha_beta, gamma))
- {
- /* The "gcd-test" has determined that there is no integer
- solution, i.e. there is no dependence. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- }
-
- /* Both access functions are univariate. This includes SIV and MIV cases. */
- else if (nb_vars_a == 1 && nb_vars_b == 1)
- {
- /* Both functions should have the same evolution sign. */
- if (((A[0][0] > 0 && -A[1][0] > 0)
- || (A[0][0] < 0 && -A[1][0] < 0)))
- {
- /* The solutions are given by:
- |
- | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
- | [u21 u22] [y0]
-
- 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:
-
- | x0 = i0 + i1 * t,
- | y0 = j0 + j1 * t. */
-
- int i0, j0, i1, j1;
-
- /* 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). */
- int x0, y0;
- int niter, niter_a, niter_b;
- tree numiter_a, numiter_b;
-
- numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
- numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
-
- if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- goto end_analyze_subs_aa;
- }
-
- niter_a = int_cst_value (numiter_a);
- niter_b = int_cst_value (numiter_b);
- niter = MIN (niter_a, niter_b);
-
- i0 = U[0][0] * gamma / gcd_alpha_beta;
- j0 = U[0][1] * gamma / gcd_alpha_beta;
- i1 = U[1][0];
- j1 = U[1][1];
-
- if ((i1 == 0 && i0 < 0)
- || (j1 == 0 && 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;
- *last_conflicts = integer_zero_node;
- }
-
- else
- {
- if (i1 > 0)
- {
- tau1 = CEIL (-i0, i1);
- tau2 = FLOOR_DIV (niter - i0, i1);
-
- if (j1 > 0)
- {
- int last_conflict, min_multiple;
- tau1 = MAX (tau1, CEIL (-j0, j1));
- tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
-
- x0 = i1 * tau1 + i0;
- y0 = j1 * tau1 + j0;
-
- /* At this point (x0, y0) is one of the
- solutions to the Diophantine equation. The
- next step has to compute the smallest
- positive solution: the first conflicts. */
- min_multiple = MIN (x0 / i1, y0 / j1);
- x0 -= i1 * min_multiple;
- y0 -= j1 * min_multiple;
-
- tau1 = (x0 - i0)/i1;
- last_conflict = tau2 - tau1;
-
- /* If the overlap occurs outside of the bounds of the
- loop, there is no dependence. */
- if (x0 > niter || y0 > niter)
- {
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- }
- else
- {
- *overlaps_a = build_polynomial_chrec
- (1,
- build_int_cst (NULL_TREE, x0),
- build_int_cst (NULL_TREE, i1));
- *overlaps_b = build_polynomial_chrec
- (1,
- build_int_cst (NULL_TREE, y0),
- build_int_cst (NULL_TREE, j1));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
- }
- }
- else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for j is not checked. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
- }
-
- else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for i is not checked. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
- }
- }
- else
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
- }
-
- else
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
-
-end_analyze_subs_aa:
- 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");
- fprintf (dump_file, ")\n");
- }
-}
-
-/* Returns true when analyze_subscript_affine_affine can be used for
- determining the dependence relation between chrec_a and chrec_b,
- that contain symbols. This function modifies chrec_a and chrec_b
- such that the analysis result is the same, and such that they don't
- contain symbols, and then can safely be passed to the analyzer.
-
- Example: The analysis of the following tuples of evolutions produce
- the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
- vs. {0, +, 1}_1
-
- {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
- {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
-*/
-
-static bool
-can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
-{
- tree diff, type, left_a, left_b, right_b;
-
- if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
- || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
- /* FIXME: For the moment not handled. Might be refined later. */
- return false;
-
- type = chrec_type (*chrec_a);
- left_a = CHREC_LEFT (*chrec_a);
- left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
- diff = chrec_fold_minus (type, left_a, left_b);
-
- if (!evolution_function_is_constant_p (diff))
- return false;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
-
- *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
- diff, CHREC_RIGHT (*chrec_a));
- right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
- *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
- build_int_cst (type, 0),
- right_b);
- return true;
-}
-
-/* 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,
- tree *last_conflicts)
-{
- dependence_stats.num_siv++;
-
- 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, last_conflicts);
-
- else if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_constant_p (chrec_b))
- analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
- overlaps_b, overlaps_a, last_conflicts);
-
- else if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_affine_p (chrec_b))
- {
- if (!chrec_contains_symbols (chrec_a)
- && !chrec_contains_symbols (chrec_b))
- {
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b,
- last_conflicts);
-
- if (*overlaps_a == chrec_dont_know
- || *overlaps_b == chrec_dont_know)
- dependence_stats.num_siv_unimplemented++;
- else if (*overlaps_a == chrec_known
- || *overlaps_b == chrec_known)
- dependence_stats.num_siv_independent++;
- else
- dependence_stats.num_siv_dependent++;
- }
- else if (can_use_analyze_subscript_affine_affine (&chrec_a,
- &chrec_b))
- {
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b,
- last_conflicts);
- /* FIXME: The number of iterations is a symbolic expression.
- Compute it properly. */
- *last_conflicts = chrec_dont_know;
-
- if (*overlaps_a == chrec_dont_know
- || *overlaps_b == chrec_dont_know)
- dependence_stats.num_siv_unimplemented++;
- else if (*overlaps_a == chrec_known
- || *overlaps_b == chrec_known)
- dependence_stats.num_siv_independent++;
- else
- dependence_stats.num_siv_dependent++;
- }
- else
- goto siv_subscript_dontknow;
- }
-
- else
- {
- siv_subscript_dontknow:;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "siv test failed: unimplemented.\n");
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_siv_unimplemented++;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Return true when the property can be computed. RES should contain
- true when calling the first time this function, then it is set to
- false when one of the evolution steps of an affine CHREC does not
- divide the constant CST. */
-
-static bool
-chrec_steps_divide_constant_p (tree chrec,
- tree cst,
- bool *res)
-{
- switch (TREE_CODE (chrec))
- {
- case POLYNOMIAL_CHREC:
- if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
- {
- if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
- /* Keep RES to true, and iterate on other dimensions. */
- return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
-
- *res = false;
- return true;
- }
- else
- /* When the step is a parameter the result is undetermined. */
- return false;
-
- 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,
- tree *last_conflicts)
-{
- /* 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).
- */
- bool divide_p = true;
- tree difference;
- dependence_stats.num_miv++;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_miv_subscript \n");
-
- chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
- chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
-
- if (eq_evolutions_p (chrec_a, chrec_b))
- {
- /* Access functions are the same: all the elements are accessed
- in the same order. */
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
- dependence_stats.num_miv_dependent++;
- }
-
- 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, &divide_p)
- && !divide_p)
- {
- /* 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;
- *last_conflicts = integer_zero_node;
- dependence_stats.num_miv_independent++;
- }
-
- else if (evolution_function_is_affine_multivariate_p (chrec_a)
- && !chrec_contains_symbols (chrec_a)
- && evolution_function_is_affine_multivariate_p (chrec_b)
- && !chrec_contains_symbols (chrec_b))
- {
- /* testsuite/.../ssa-chrec-35.c
- {0, +, 1}_2 vs. {0, +, 1}_3
- the overlapping elements are respectively located at iterations:
- {0, +, 1}_x and {0, +, 1}_x,
- in other words, we have the equality:
- {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
-
- Other examples:
- {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
- {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
-
- {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
- {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
- */
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b, last_conflicts);
-
- if (*overlaps_a == chrec_dont_know
- || *overlaps_b == chrec_dont_know)
- dependence_stats.num_miv_unimplemented++;
- else if (*overlaps_a == chrec_known
- || *overlaps_b == chrec_known)
- dependence_stats.num_miv_independent++;
- else
- dependence_stats.num_miv_dependent++;
- }
-
- else
- {
- /* When the analysis is too difficult, answer "don't know". */
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
-
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- dependence_stats.num_miv_unimplemented++;
- }
-
- 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,
- tree *last_conflicts)
-{
- dependence_stats.num_subscript_tests++;
-
- 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))
- {
- dependence_stats.num_subscript_undetermined++;
-
- *overlap_iterations_a = chrec_dont_know;
- *overlap_iterations_b = chrec_dont_know;
- }
-
- /* If they are the same chrec, and are affine, they overlap
- on every iteration. */
- else if (eq_evolutions_p (chrec_a, chrec_b)
- && evolution_function_is_affine_multivariate_p (chrec_a))
- {
- dependence_stats.num_same_subscript_function++;
- *overlap_iterations_a = integer_zero_node;
- *overlap_iterations_b = integer_zero_node;
- *last_conflicts = chrec_dont_know;
- }
-
- /* If they aren't the same, and aren't affine, we can't do anything
- yet. */
- else if ((chrec_contains_symbols (chrec_a)
- || chrec_contains_symbols (chrec_b))
- && (!evolution_function_is_affine_multivariate_p (chrec_a)
- || !evolution_function_is_affine_multivariate_p (chrec_b)))
- {
- dependence_stats.num_subscript_undetermined++;
- *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,
- last_conflicts);
-
- else if (siv_subscript_p (chrec_a, chrec_b))
- analyze_siv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b,
- last_conflicts);
-
- else
- analyze_miv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b,
- last_conflicts);
-
- 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");
- fprintf (dump_file, ")\n");
- }
-}
-
-/* Helper function for uniquely inserting distance vectors. */
-
-static void
-save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
-{
- unsigned i;
- lambda_vector v;
-
- for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
- if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
- return;
-
- VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
-}
-
-/* Helper function for uniquely inserting direction vectors. */
-
-static void
-save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
-{
- unsigned i;
- lambda_vector v;
-
- for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
- if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
- return;
-
- VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
-}
-
-/* Add a distance of 1 on all the loops outer than INDEX. If we
- haven't yet determined a distance for this outer loop, push a new
- distance vector composed of the previous distance, and a distance
- of 1 for this outer loop. Example:
-
- | loop_1
- | loop_2
- | A[10]
- | endloop_2
- | endloop_1
-
- Saved vectors are of the form (dist_in_1, dist_in_2). First, we
- save (0, 1), then we have to save (1, 0). */
-
-static void
-add_outer_distances (struct data_dependence_relation *ddr,
- lambda_vector dist_v, int index)
-{
- /* For each outer loop where init_v is not set, the accesses are
- in dependence of distance 1 in the loop. */
- while (--index >= 0)
- {
- lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
- save_v[index] = 1;
- save_dist_v (ddr, save_v);
- }
-}
-
-/* Return false when fail to represent the data dependence as a
- distance vector. INIT_B is set to true when a component has been
- added to the distance vector DIST_V. INDEX_CARRY is then set to
- the index in DIST_V that carries the dependence. */
-
-static bool
-build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
- struct data_reference *ddr_a,
- struct data_reference *ddr_b,
- lambda_vector dist_v, bool *init_b,
- int *index_carry)
-{
- unsigned i;
- lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree access_fn_a, access_fn_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- {
- non_affine_dependence_relation (ddr);
- return false;
- }
-
- access_fn_a = DR_ACCESS_FN (ddr_a, i);
- access_fn_b = DR_ACCESS_FN (ddr_b, i);
-
- if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
- && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
- {
- int dist, index;
- int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
- DDR_LOOP_NEST (ddr));
- int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
- DDR_LOOP_NEST (ddr));
-
- /* The dependence is carried by the outermost loop. Example:
- | loop_1
- | A[{4, +, 1}_1]
- | loop_2
- | A[{5, +, 1}_2]
- | endloop_2
- | endloop_1
- In this case, the dependence is carried by loop_1. */
- index = index_a < index_b ? index_a : index_b;
- *index_carry = MIN (index, *index_carry);
-
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- {
- non_affine_dependence_relation (ddr);
- return false;
- }
-
- dist = int_cst_value (SUB_DISTANCE (subscript));
-
- /* This is the subscript coupling test. If we have already
- recorded a distance for this loop (a distance coming from
- another subscript), it should be the same. For example,
- in the following code, there is no dependence:
-
- | loop i = 0, N, 1
- | T[i+1][i] = ...
- | ... = T[i][i]
- | endloop
- */
- if (init_v[index] != 0 && dist_v[index] != dist)
- {
- finalize_ddr_dependent (ddr, chrec_known);
- return false;
- }
-
- dist_v[index] = dist;
- init_v[index] = 1;
- *init_b = true;
- }
- else
- {
- /* This can be for example an affine vs. constant dependence
- (T[i] vs. T[3]) that is not an affine dependence and is
- not representable as a distance vector. */
- non_affine_dependence_relation (ddr);
- return false;
- }
- }
-
- return true;
-}
-
-/* Return true when the DDR contains two data references that have the
- same access functions. */
-
-static bool
-same_access_functions (struct data_dependence_relation *ddr)
-{
- unsigned i;
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
- DR_ACCESS_FN (DDR_B (ddr), i)))
- return false;
-
- return true;
-}
-
-/* Helper function for the case where DDR_A and DDR_B are the same
- multivariate access function. */
-
-static void
-add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
-{
- int x_1, x_2;
- tree c_1 = CHREC_LEFT (c_2);
- tree c_0 = CHREC_LEFT (c_1);
- lambda_vector dist_v;
-
- /* Polynomials with more than 2 variables are not handled yet. */
- if (TREE_CODE (c_0) != INTEGER_CST)
- {
- DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
- return;
- }
-
- x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
- x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
-
- /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
- dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
- dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
- save_dist_v (ddr, dist_v);
-
- add_outer_distances (ddr, dist_v, x_1);
-}
-
-/* Helper function for the case where DDR_A and DDR_B are the same
- access functions. */
-
-static void
-add_other_self_distances (struct data_dependence_relation *ddr)
-{
- lambda_vector dist_v;
- unsigned i;
- int index_carry = DDR_NB_LOOPS (ddr);
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
-
- if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
- {
- if (!evolution_function_is_univariate_p (access_fun))
- {
- if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
- {
- DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
- return;
- }
-
- add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
- return;
- }
-
- index_carry = MIN (index_carry,
- index_in_loop_nest (CHREC_VARIABLE (access_fun),
- DDR_LOOP_NEST (ddr)));
- }
- }
-
- dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- add_outer_distances (ddr, dist_v, index_carry);
-}
-
-/* Compute the classic per loop distance vector. DDR is the data
- dependence relation to build a vector from. Return false when fail
- to represent the data dependence as a distance vector. */
-
-static bool
-build_classic_dist_vector (struct data_dependence_relation *ddr)
-{
- bool init_b = false;
- int index_carry = DDR_NB_LOOPS (ddr);
- lambda_vector dist_v;
-
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
-
- if (same_access_functions (ddr))
- {
- /* Save the 0 vector. */
- dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- save_dist_v (ddr, dist_v);
-
- if (DDR_NB_LOOPS (ddr) > 1)
- add_other_self_distances (ddr);
-
- return true;
- }
-
- dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
- dist_v, &init_b, &index_carry))
- return false;
-
- /* Save the distance vector if we initialized one. */
- if (init_b)
- {
- /* Verify a basic constraint: classic distance vectors should
- always be lexicographically positive.
-
- Data references are collected in the order of execution of
- the program, thus for the following loop
-
- | for (i = 1; i < 100; i++)
- | for (j = 1; j < 100; j++)
- | {
- | t = T[j+1][i-1]; // A
- | T[j][i] = t + 2; // B
- | }
-
- references are collected following the direction of the wind:
- A then B. The data dependence tests are performed also
- following this order, such that we're looking at the distance
- separating the elements accessed by A from the elements later
- accessed by B. But in this example, the distance returned by
- test_dep (A, B) is lexicographically negative (-1, 1), that
- means that the access A occurs later than B with respect to
- the outer loop, ie. we're actually looking upwind. In this
- case we solve test_dep (B, A) looking downwind to the
- lexicographically positive solution, that returns the
- distance vector (1, -1). */
- if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
- {
- lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
- compute_subscript_distance (ddr);
- build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- save_v, &init_b, &index_carry);
- save_dist_v (ddr, save_v);
-
- /* In this case there is a dependence forward for all the
- outer loops:
-
- | for (k = 1; k < 100; k++)
- | for (i = 1; i < 100; i++)
- | for (j = 1; j < 100; j++)
- | {
- | t = T[j+1][i-1]; // A
- | T[j][i] = t + 2; // B
- | }
-
- the vectors are:
- (0, 1, -1)
- (1, 1, -1)
- (1, -1, 1)
- */
- if (DDR_NB_LOOPS (ddr) > 1)
- {
- add_outer_distances (ddr, save_v, index_carry);
- add_outer_distances (ddr, dist_v, index_carry);
- }
- }
- else
- {
- lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
- lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
- save_dist_v (ddr, save_v);
-
- if (DDR_NB_LOOPS (ddr) > 1)
- {
- lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
-
- subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
- compute_subscript_distance (ddr);
- build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
- opposite_v, &init_b, &index_carry);
-
- add_outer_distances (ddr, dist_v, index_carry);
- add_outer_distances (ddr, opposite_v, index_carry);
- }
- }
- }
- else
- {
- /* 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
- */
- add_outer_distances (ddr, dist_v,
- lambda_vector_first_nz (dist_v,
- DDR_NB_LOOPS (ddr), 0));
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- unsigned i;
-
- fprintf (dump_file, "(build_classic_dist_vector\n");
- for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
- {
- fprintf (dump_file, " dist_vector = (");
- print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
- DDR_NB_LOOPS (ddr));
- fprintf (dump_file, " )\n");
- }
- fprintf (dump_file, ")\n");
- }
-
- return true;
-}
-
-/* Return the direction for a given distance.
- FIXME: Computing dir this way is suboptimal, since dir can catch
- cases that dist is unable to represent. */
-
-static inline enum data_dependence_direction
-dir_from_dist (int dist)
-{
- if (dist > 0)
- return dir_positive;
- else if (dist < 0)
- return dir_negative;
- else
- return dir_equal;
-}
-
-/* Compute the classic per loop direction vector. DDR is the data
- dependence relation to build a vector from. */
-
-static void
-build_classic_dir_vector (struct data_dependence_relation *ddr)
-{
- unsigned i, j;
- lambda_vector dist_v;
-
- for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
- {
- lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
-
- for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
- dir_v[j] = dir_from_dist (dist_v[j]);
-
- save_dir_v (ddr, dir_v);
- }
-}
-
-/* Helper function. Returns true when there is a dependence between
- data references DRA and DRB. */
-
-static bool
-subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
- struct data_reference *dra,
- struct data_reference *drb)
-{
- unsigned int i;
- tree last_conflicts;
- struct subscript *subscript;
-
- for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
- i++)
- {
- tree overlaps_a, overlaps_b;
-
- analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
- DR_ACCESS_FN (drb, i),
- &overlaps_a, &overlaps_b,
- &last_conflicts);
-
- if (chrec_contains_undetermined (overlaps_a)
- || chrec_contains_undetermined (overlaps_b))
- {
- finalize_ddr_dependent (ddr, chrec_dont_know);
- dependence_stats.num_dependence_undetermined++;
- return false;
- }
-
- else if (overlaps_a == chrec_known
- || overlaps_b == chrec_known)
- {
- finalize_ddr_dependent (ddr, chrec_known);
- dependence_stats.num_dependence_independent++;
- return false;
- }
-
- else
- {
- SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
- SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
- SUB_LAST_CONFLICT (subscript) = last_conflicts;
- }
- }
-
- return true;
-}
-
-/* Computes the conflicting iterations, and initialize DDR. */
-
-static void
-subscript_dependence_tester (struct data_dependence_relation *ddr)
-{
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(subscript_dependence_tester \n");
-
- if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
- dependence_stats.num_dependence_dependent++;
-
- compute_subscript_distance (ddr);
- if (build_classic_dist_vector (ddr))
- build_classic_dir_vector (ddr);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* 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;
- VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
- tree t;
-
- for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
- if (!evolution_function_is_constant_p (t)
- && !evolution_function_is_affine_multivariate_p (t))
- 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. */
-
-static 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\n");
- 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)
- {
- dependence_stats.num_dependence_tests++;
-
- 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
- {
- dependence_stats.num_dependence_undetermined++;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Data ref a:\n");
- dump_data_reference (dump_file, dra);
- fprintf (dump_file, "Data ref b:\n");
- dump_data_reference (dump_file, drb);
- fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
- }
- finalize_ddr_dependent (ddr, chrec_dont_know);
- }
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* This computes the dependence relation for the same data
- reference into DDR. */
-
-static void
-compute_self_dependence (struct data_dependence_relation *ddr)
-{
- unsigned int i;
- struct subscript *subscript;
-
- for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
- i++)
- {
- /* The accessed index overlaps for each iteration. */
- SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
- SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
- SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
- }
-
- /* The distance vector is the zero vector. */
- save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
- save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
-}
-
-/* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
- the data references in DATAREFS, in the LOOP_NEST. When
- COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
- relations. */
-
-static void
-compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
- VEC (ddr_p, heap) **dependence_relations,
- VEC (loop_p, heap) *loop_nest,
- bool compute_self_and_rr)
-{
- struct data_dependence_relation *ddr;
- struct data_reference *a, *b;
- unsigned int i, j;
-
- for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
- for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
- if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
- {
- ddr = initialize_data_dependence_relation (a, b, loop_nest);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_affine_dependence (ddr);
- }
-
- if (compute_self_and_rr)
- for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
- {
- ddr = initialize_data_dependence_relation (a, a, loop_nest);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_self_dependence (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.
-
- TODO: This function should be made smarter so that it can handle address
- arithmetic as if they were array accesses, etc. */
-
-tree
-find_data_references_in_loop (struct loop *loop,
- VEC (data_reference_p, heap) **datarefs)
-{
- basic_block bb, *bbs;
- unsigned int i;
- block_stmt_iterator bsi;
- struct data_reference *dr;
-
- bbs = get_loop_body (loop);
-
- for (i = 0; i < loop->num_nodes; i++)
- {
- bb = bbs[i];
-
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- {
- tree stmt = bsi_stmt (bsi);
-
- /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
- Calls have side-effects, except those to const or pure
- functions. */
- if ((TREE_CODE (stmt) == CALL_EXPR
- && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
- || (TREE_CODE (stmt) == ASM_EXPR
- && ASM_VOLATILE_P (stmt)))
- goto insert_dont_know_node;
-
- if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
- continue;
-
- switch (TREE_CODE (stmt))
- {
- case MODIFY_EXPR:
- {
- bool one_inserted = false;
- tree opnd0 = TREE_OPERAND (stmt, 0);
- tree opnd1 = TREE_OPERAND (stmt, 1);
-
- if (TREE_CODE (opnd0) == ARRAY_REF
- || TREE_CODE (opnd0) == INDIRECT_REF
- || TREE_CODE (opnd0) == COMPONENT_REF)
- {
- dr = create_data_ref (opnd0, stmt, false);
- if (dr)
- {
- VEC_safe_push (data_reference_p, heap, *datarefs, dr);
- one_inserted = true;
- }
- }
-
- if (TREE_CODE (opnd1) == ARRAY_REF
- || TREE_CODE (opnd1) == INDIRECT_REF
- || TREE_CODE (opnd1) == COMPONENT_REF)
- {
- dr = create_data_ref (opnd1, stmt, true);
- if (dr)
- {
- VEC_safe_push (data_reference_p, heap, *datarefs, dr);
- one_inserted = true;
- }
- }
-
- if (!one_inserted)
- goto insert_dont_know_node;
-
- break;
- }
-
- case CALL_EXPR:
- {
- tree args;
- bool one_inserted = false;
-
- for (args = TREE_OPERAND (stmt, 1); args;
- args = TREE_CHAIN (args))
- if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
- || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF
- || TREE_CODE (TREE_VALUE (args)) == COMPONENT_REF)
- {
- dr = create_data_ref (TREE_VALUE (args), stmt, true);
- if (dr)
- {
- VEC_safe_push (data_reference_p, heap, *datarefs, dr);
- one_inserted = true;
- }
- }
-
- if (!one_inserted)
- goto insert_dont_know_node;
-
- break;
- }
-
- default:
- {
- struct data_reference *res;
-
- insert_dont_know_node:;
- res = XNEW (struct data_reference);
- DR_STMT (res) = NULL_TREE;
- DR_REF (res) = NULL_TREE;
- DR_BASE_OBJECT (res) = NULL;
- DR_TYPE (res) = ARRAY_REF_TYPE;
- DR_SET_ACCESS_FNS (res, NULL);
- DR_BASE_OBJECT (res) = NULL;
- DR_IS_READ (res) = false;
- DR_BASE_ADDRESS (res) = NULL_TREE;
- DR_OFFSET (res) = NULL_TREE;
- DR_INIT (res) = NULL_TREE;
- DR_STEP (res) = NULL_TREE;
- DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
- DR_MEMTAG (res) = NULL_TREE;
- DR_PTR_INFO (res) = NULL;
- VEC_safe_push (data_reference_p, heap, *datarefs, res);
-
- free (bbs);
- return chrec_dont_know;
- }
- }
-
- /* When there are no defs in the loop, the loop is parallel. */
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
- loop->parallel_p = false;
- }
- }
-
- free (bbs);
-
- return NULL_TREE;
-}
-
-/* Recursive helper function. */
-
-static bool
-find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
-{
- /* Inner loops of the nest should not contain siblings. Example:
- when there are two consecutive loops,
-
- | loop_0
- | loop_1
- | A[{0, +, 1}_1]
- | endloop_1
- | loop_2
- | A[{0, +, 1}_2]
- | endloop_2
- | endloop_0
-
- the dependence relation cannot be captured by the distance
- abstraction. */
- if (loop->next)
- return false;
-
- VEC_safe_push (loop_p, heap, *loop_nest, loop);
- if (loop->inner)
- return find_loop_nest_1 (loop->inner, loop_nest);
- return true;
-}
-
-/* Return false when the LOOP is not well nested. Otherwise return
- true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
- contain the loops from the outermost to the innermost, as they will
- appear in the classic distance vector. */
-
-static bool
-find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
-{
- VEC_safe_push (loop_p, heap, *loop_nest, loop);
- if (loop->inner)
- return find_loop_nest_1 (loop->inner, loop_nest);
- return true;
-}
-
-/* Given a loop nest LOOP, the following vectors are returned:
- DATAREFS is initialized to all the array elements contained in this loop,
- DEPENDENCE_RELATIONS contains the relations between the data references.
- Compute read-read and self relations if
- COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
-
-void
-compute_data_dependences_for_loop (struct loop *loop,
- bool compute_self_and_read_read_dependences,
- VEC (data_reference_p, heap) **datarefs,
- VEC (ddr_p, heap) **dependence_relations)
-{
- struct loop *loop_nest = loop;
- VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
-
- memset (&dependence_stats, 0, sizeof (dependence_stats));
-
- /* If the loop nest is not well formed, or one of the data references
- is not computable, give up without spending time to compute other
- dependences. */
- if (!loop_nest
- || !find_loop_nest (loop_nest, &vloops)
- || 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, vloops);
- VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- }
- else
- compute_all_dependences (*datarefs, dependence_relations, vloops,
- compute_self_and_read_read_dependences);
-
- if (dump_file && (dump_flags & TDF_STATS))
- {
- fprintf (dump_file, "Dependence tester statistics:\n");
-
- fprintf (dump_file, "Number of dependence tests: %d\n",
- dependence_stats.num_dependence_tests);
- fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
- dependence_stats.num_dependence_dependent);
- fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
- dependence_stats.num_dependence_independent);
- fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
- dependence_stats.num_dependence_undetermined);
-
- fprintf (dump_file, "Number of subscript tests: %d\n",
- dependence_stats.num_subscript_tests);
- fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
- dependence_stats.num_subscript_undetermined);
- fprintf (dump_file, "Number of same subscript function: %d\n",
- dependence_stats.num_same_subscript_function);
-
- fprintf (dump_file, "Number of ziv tests: %d\n",
- dependence_stats.num_ziv);
- fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
- dependence_stats.num_ziv_dependent);
- fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
- dependence_stats.num_ziv_independent);
- fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
- dependence_stats.num_ziv_unimplemented);
-
- fprintf (dump_file, "Number of siv tests: %d\n",
- dependence_stats.num_siv);
- fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
- dependence_stats.num_siv_dependent);
- fprintf (dump_file, "Number of siv tests returning independent: %d\n",
- dependence_stats.num_siv_independent);
- fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
- dependence_stats.num_siv_unimplemented);
-
- fprintf (dump_file, "Number of miv tests: %d\n",
- dependence_stats.num_miv);
- fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
- dependence_stats.num_miv_dependent);
- fprintf (dump_file, "Number of miv tests returning independent: %d\n",
- dependence_stats.num_miv_independent);
- fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
- dependence_stats.num_miv_unimplemented);
- }
-}
-
-/* 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. */
-#if 0
-static void
-analyze_all_data_dependences (struct loops *loops)
-{
- unsigned int i;
- int nb_data_refs = 10;
- VEC (data_reference_p, heap) *datarefs =
- VEC_alloc (data_reference_p, heap, nb_data_refs);
- VEC (ddr_p, heap) *dependence_relations =
- VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
-
- /* Compute DDs on the whole function. */
- compute_data_dependences_for_loop (loops->parray[0], false,
- &datarefs, &dependence_relations);
-
- if (dump_file)
- {
- dump_data_dependence_relations (dump_file, dependence_relations);
- fprintf (dump_file, "\n\n");
-
- if (dump_flags & TDF_DETAILS)
- dump_dist_dir_vectors (dump_file, dependence_relations);
-
- if (dump_flags & TDF_STATS)
- {
- unsigned nb_top_relations = 0;
- unsigned nb_bot_relations = 0;
- unsigned nb_basename_differ = 0;
- unsigned nb_chrec_relations = 0;
- struct data_dependence_relation *ddr;
-
- for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); 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);
- bool differ_p;
-
- if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
- && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
- || (base_object_differ_p (a, b, &differ_p)
- && differ_p))
- nb_basename_differ++;
- else
- nb_bot_relations++;
- }
-
- else
- nb_chrec_relations++;
- }
-
- gather_stats_on_scev_database ();
- }
- }
-
- free_dependence_relations (dependence_relations);
- free_data_refs (datarefs);
-}
-#endif
-
-/* Free the memory used by a data dependence relation DDR. */
-
-void
-free_dependence_relation (struct data_dependence_relation *ddr)
-{
- if (ddr == NULL)
- return;
-
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
- VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
-
- free (ddr);
-}
-
-/* Free the memory used by the data dependence relations from
- DEPENDENCE_RELATIONS. */
-
-void
-free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
-{
- unsigned int i;
- struct data_dependence_relation *ddr;
- VEC (loop_p, heap) *loop_nest = NULL;
-
- for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
- {
- if (ddr == NULL)
- continue;
- if (loop_nest == NULL)
- loop_nest = DDR_LOOP_NEST (ddr);
- else
- gcc_assert (DDR_LOOP_NEST (ddr) == NULL
- || DDR_LOOP_NEST (ddr) == loop_nest);
- free_dependence_relation (ddr);
- }
-
- if (loop_nest)
- VEC_free (loop_p, heap, loop_nest);
- VEC_free (ddr_p, heap, dependence_relations);
-}
-
-/* Free the memory used by the data references from DATAREFS. */
-
-void
-free_data_refs (VEC (data_reference_p, heap) *datarefs)
-{
- unsigned int i;
- struct data_reference *dr;
-
- for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
- free_data_ref (dr);
- VEC_free (data_reference_p, heap, datarefs);
-}
-