X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-data-ref.c;h=2715339219e2b0443a850a8db82dd5348cd1e6a5;hb=49b6dba67f06de2ec02bf958c556fc34b171408e;hp=3f24c6a51473dbdea6812554f0493aad719ff1a4;hpb=d97e22fb65bb6365d79ae4f291981c27bc0f954a;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 3f24c6a5147..2715339219e 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -6,7 +6,7 @@ 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 +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -15,9 +15,8 @@ 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. */ +along with GCC; see the file COPYING3. If not see +. */ /* This pass walks a given loop structure searching for array references. The information about the array accesses is recorded @@ -89,7 +88,6 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #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" @@ -122,467 +120,14 @@ static struct datadep_stats 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 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 = symbol_mem_tag (SSA_NAME_VAR (ptr)); - 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); - bitmap bal1, bal2; - - 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 = symbol_mem_tag (SSA_NAME_VAR (ptr_a)); - if (!tag_a) - tag_a = DR_MEMTAG (dra); - if (!tag_a) - return false; - - tag_b = symbol_mem_tag (SSA_NAME_VAR (ptr_b)); - if (!tag_b) - tag_b = DR_MEMTAG (drb); - if (!tag_b) - return false; - } - bal1 = BITMAP_ALLOC (NULL); - bitmap_set_bit (bal1, DECL_UID (tag_a)); - if (MTAG_P (tag_a) && MTAG_ALIASES (tag_a)) - bitmap_ior_into (bal1, MTAG_ALIASES (tag_a)); - - bal2 = BITMAP_ALLOC (NULL); - bitmap_set_bit (bal2, DECL_UID (tag_b)); - if (MTAG_P (tag_b) && MTAG_ALIASES (tag_b)) - bitmap_ior_into (bal2, MTAG_ALIASES (tag_b)); - *aliased = bitmap_intersect_p (bal1, bal2); - - BITMAP_FREE (bal1); - BITMAP_FREE (bal2); - 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; - tree decl_a, decl_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 restricted pointer, - in the same block/scope. */ - else if (TYPE_RESTRICT (type_a) - && TYPE_RESTRICT (type_b) - && (!DR_IS_READ (drb) || !DR_IS_READ (dra)) - && TREE_CODE (DR_BASE_ADDRESS (dra)) == SSA_NAME - && (decl_a = SSA_NAME_VAR (DR_BASE_ADDRESS (dra))) - && TREE_CODE (decl_a) == PARM_DECL - && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL - && TREE_CODE (DR_BASE_ADDRESS (drb)) == SSA_NAME - && (decl_b = SSA_NAME_VAR (DR_BASE_ADDRESS (drb))) - && TREE_CODE (decl_b) == PARM_DECL - && TREE_CODE (DECL_CONTEXT (decl_b)) == FUNCTION_DECL - && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b)) - { - *differ_p = true; - return true; - } - - return false; -} - + struct data_reference *, + struct loop *); /* Returns true iff A divides B. */ static inline bool -tree_fold_divides_p (tree a, tree b) +tree_fold_divides_p (const_tree a, const_tree b) { gcc_assert (TREE_CODE (a) == INTEGER_CST); gcc_assert (TREE_CODE (b) == INTEGER_CST); @@ -611,6 +156,14 @@ dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs) dump_data_reference (file, dr); } +/* Dump to STDERR all the dependence relations from DDRS. */ + +void +debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs) +{ + dump_data_dependence_relations (stderr, ddrs); +} + /* Dump into FILE all the dependence relations from DDRS. */ void @@ -633,7 +186,7 @@ dump_data_reference (FILE *outf, unsigned int i; fprintf (outf, "(Data Ref: \n stmt: "); - print_generic_stmt (outf, DR_STMT (dr), 0); + print_gimple_stmt (outf, DR_STMT (dr), 0, 0); fprintf (outf, " ref: "); print_generic_stmt (outf, DR_REF (dr), 0); fprintf (outf, " base_object: "); @@ -805,13 +358,20 @@ dump_data_dependence_relation (FILE *outf, { struct data_reference *dra, *drb; + fprintf (outf, "(Data Dep: \n"); + + if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + { + fprintf (outf, " (don't know)\n)\n"); + return; + } + 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) + dump_data_reference (outf, dra); + dump_data_reference (outf, drb); + + if (DDR_ARE_DEPENDENT (ddr) == chrec_known) fprintf (outf, " (no dependence)\n"); else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) @@ -940,1225 +500,522 @@ dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs) fprintf (file, "\n\n"); } - - -/* 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]". - The function returns the base name: "A". */ +/* Helper function for split_constant_offset. Expresses OP0 CODE OP1 + (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero + constant of type ssizetype, and returns true. If we cannot do this + with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false + is returned. */ -static tree -analyze_array_indexes (struct loop *loop, - VEC(tree,heap) **access_fns, - tree ref, tree stmt) +static bool +split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, + tree *var, tree *off) { - tree opnd0, opnd1; - tree access_fn; + tree var0, var1; + tree off0, off1; + enum tree_code ocode = code; - opnd0 = TREE_OPERAND (ref, 0); - opnd1 = TREE_OPERAND (ref, 1); + *var = NULL_TREE; + *off = NULL_TREE; - /* 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)); + switch (code) + { + case INTEGER_CST: + *var = build_int_cst (type, 0); + *off = fold_convert (ssizetype, op0); + return true; - 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); + case POINTER_PLUS_EXPR: + ocode = PLUS_EXPR; + /* FALLTHROUGH */ + case PLUS_EXPR: + case MINUS_EXPR: + split_constant_offset (op0, &var0, &off0); + split_constant_offset (op1, &var1, &off1); + *var = fold_build2 (code, type, var0, var1); + *off = size_binop (ocode, off0, off1); + return true; - /* Return the base name of the data access. */ - else - return opnd0; -} + case MULT_EXPR: + if (TREE_CODE (op1) != INTEGER_CST) + return false; -/* 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. */ + split_constant_offset (op0, &var0, &off0); + *var = fold_build2 (MULT_EXPR, type, var0, op1); + *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1)); + return true; -static struct data_reference * -init_array_ref (tree stmt, tree ref, bool is_read) -{ - struct loop *loop = loop_containing_stmt (stmt); - VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3); - struct data_reference *res = XNEW (struct data_reference);; + case ADDR_EXPR: + { + tree base, poffset; + HOST_WIDE_INT pbitsize, pbitpos; + enum machine_mode pmode; + int punsignedp, pvolatilep; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "(init_array_ref \n"); - fprintf (dump_file, " (ref = "); - print_generic_stmt (dump_file, ref, 0); - fprintf (dump_file, ")\n"); - } + op0 = TREE_OPERAND (op0, 0); + if (!handled_component_p (op0)) + return false; - DR_STMT (res) = stmt; - DR_REF (res) = ref; - DR_BASE_OBJECT (res) = analyze_array_indexes (loop, &acc_fns, ref, stmt); - 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; + base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset, + &pmode, &punsignedp, &pvolatilep, false); - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); + if (pbitpos % BITS_PER_UNIT != 0) + return false; + base = build_fold_addr_expr (base); + off0 = ssize_int (pbitpos / BITS_PER_UNIT); - return res; + if (poffset) + { + split_constant_offset (poffset, &poffset, &off1); + off0 = size_binop (PLUS_EXPR, off0, off1); + if (POINTER_TYPE_P (TREE_TYPE (base))) + base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base), + base, fold_convert (sizetype, poffset)); + else + base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, + fold_convert (TREE_TYPE (base), poffset)); + } + + var0 = fold_convert (type, base); + + /* If variable length types are involved, punt, otherwise casts + might be converted into ARRAY_REFs in gimplify_conversion. + To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which + possibly no longer appears in current GIMPLE, might resurface. + This perhaps could run + if (CONVERT_EXPR_P (var0)) + { + gimplify_conversion (&var0); + // Attempt to fill in any within var0 found ARRAY_REF's + // element size from corresponding op embedded ARRAY_REF, + // if unsuccessful, just punt. + } */ + while (POINTER_TYPE_P (type)) + type = TREE_TYPE (type); + if (int_size_in_bytes (type) < 0) + return false; + + *var = var0; + *off = off0; + return true; + } + + case SSA_NAME: + { + gimple def_stmt = SSA_NAME_DEF_STMT (op0); + enum tree_code subcode; + + if (gimple_code (def_stmt) != GIMPLE_ASSIGN) + return false; + + var0 = gimple_assign_rhs1 (def_stmt); + subcode = gimple_assign_rhs_code (def_stmt); + var1 = gimple_assign_rhs2 (def_stmt); + + return split_constant_offset_1 (type, var0, subcode, var1, var, off); + } + + default: + return false; + } } -/* For a data reference REF contained in the statement STMT, initialize - a DATA_REFERENCE structure, and return it. */ +/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF + will be ssizetype. */ -static struct data_reference * -init_pointer_ref (tree stmt, tree ref, tree access_fn, bool is_read, - tree base_address, tree step, struct ptr_info_def *ptr_info) +void +split_constant_offset (tree exp, tree *var, tree *off) { - struct data_reference *res = XNEW (struct data_reference); - VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3); + tree type = TREE_TYPE (exp), otype, op0, op1, e, o; + enum tree_code code; - if (dump_file && (dump_flags & TDF_DETAILS)) + *var = exp; + *off = ssize_int (0); + STRIP_NOPS (exp); + + if (automatically_generated_chrec_p (exp)) + return; + + otype = TREE_TYPE (exp); + code = TREE_CODE (exp); + extract_ops_from_tree (exp, &code, &op0, &op1); + if (split_constant_offset_1 (otype, op0, code, op1, &e, &o)) { - fprintf (dump_file, "(init_pointer_ref \n"); - fprintf (dump_file, " (ref = "); - print_generic_stmt (dump_file, ref, 0); - fprintf (dump_file, ")\n"); + *var = fold_convert (type, e); + *off = o; } +} - DR_STMT (res) = stmt; - DR_REF (res) = ref; - DR_BASE_OBJECT (res) = NULL_TREE; - DR_TYPE (res) = POINTER_REF_TYPE; - 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) = NULL_TREE; - DR_INIT (res) = NULL_TREE; - DR_STEP (res) = step; - DR_OFFSET_MISALIGNMENT (res) = NULL_TREE; - DR_MEMTAG (res) = NULL_TREE; - DR_PTR_INFO (res) = ptr_info; +/* Returns the address ADDR of an object in a canonical shape (without nop + casts, and with type of pointer to the object). */ - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); +static tree +canonicalize_base_object_address (tree addr) +{ + tree orig = addr; - return res; + STRIP_NOPS (addr); + + /* The base address may be obtained by casting from integer, in that case + keep the cast. */ + if (!POINTER_TYPE_P (TREE_TYPE (addr))) + return orig; + + if (TREE_CODE (addr) != ADDR_EXPR) + return addr; + + return build_fold_addr_expr (TREE_OPERAND (addr, 0)); } -/* Analyze 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. */ +/* Analyzes the behavior of the memory reference DR in the innermost loop that + contains it. Returns true if analysis succeed or false otherwise. */ -static struct data_reference * -analyze_indirect_ref (tree stmt, tree ref, bool is_read) +bool +dr_analyze_innermost (struct data_reference *dr) { + gimple stmt = DR_STMT (dr); 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; + tree ref = DR_REF (dr); + HOST_WIDE_INT pbitsize, pbitpos; + tree base, poffset; + enum machine_mode pmode; + int punsignedp, pvolatilep; + affine_iv base_iv, offset_iv; + tree init, dinit, step; - if (TREE_CODE (ptr_ref) == SSA_NAME) - ptr_info = SSA_NAME_PTR_INFO (ptr_ref); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "analyze_innermost: "); + + base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset, + &pmode, &punsignedp, &pvolatilep, false); + gcc_assert (base != NULL_TREE); - STRIP_NOPS (init); - if (access_fn == chrec_dont_know || !init || init == chrec_dont_know) + if (pbitpos % BITS_PER_UNIT != 0) { 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; + fprintf (dump_file, "failed: bit offset alignment.\n"); + return false; } - if (dump_file && (dump_flags & TDF_DETAILS)) + base = build_fold_addr_expr (base); + if (!simple_iv (loop, stmt, base, &base_iv, false)) { - fprintf (dump_file, "\nAccess function of ptr: "); - print_generic_expr (dump_file, access_fn, TDF_SLIM); - fprintf (dump_file, "\n"); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of base is not affine.\n"); + return false; } - - if (!expr_invariant_in_loop_p (loop, init)) + if (!poffset) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\ninitial condition is not loop invariant.\n"); + offset_iv.base = ssize_int (0); + offset_iv.step = ssize_int (0); } - else + else if (!simple_iv (loop, stmt, poffset, &offset_iv, false)) { - 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"); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of offset is not affine.\n"); + return false; } - return init_pointer_ref (stmt, ref, access_fn, is_read, base_address, - step, ptr_info); -} - -/* Function strip_conversions - Strip conversions that don't narrow the mode. */ + init = ssize_int (pbitpos / BITS_PER_UNIT); + split_constant_offset (base_iv.base, &base_iv.base, &dinit); + init = size_binop (PLUS_EXPR, init, dinit); + split_constant_offset (offset_iv.base, &offset_iv.base, &dinit); + init = size_binop (PLUS_EXPR, init, dinit); -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; -} - + step = size_binop (PLUS_EXPR, + fold_convert (ssizetype, base_iv.step), + fold_convert (ssizetype, offset_iv.step)); -/* Function analyze_offset_expr + DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base); - 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. + DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base); + DR_INIT (dr) = init; + DR_STEP (dr) = step; - 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. + DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base)); - STEP is an evolution of the data reference in this loop in bytes. - In the above example, STEP is C_j. + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "success.\n"); - 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. + return true; +} -*/ +/* Determines the base object and the list of indices of memory reference + DR, analyzed in loop nest NEST. */ -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; +static void +dr_analyze_indices (struct data_reference *dr, struct loop *nest) +{ + gimple stmt = DR_STMT (dr); + struct loop *loop = loop_containing_stmt (stmt); + VEC (tree, heap) *access_fns = NULL; + tree ref = unshare_expr (DR_REF (dr)), aref = ref, op; + tree base, off, access_fn; + basic_block before_loop = block_before_loop (nest); - *step = NULL_TREE; - *misalign = NULL_TREE; - *aligned_to = NULL_TREE; - *initial_offset = NULL_TREE; + while (handled_component_p (aref)) + { + if (TREE_CODE (aref) == ARRAY_REF) + { + op = TREE_OPERAND (aref, 1); + access_fn = analyze_scalar_evolution (loop, op); + access_fn = instantiate_scev (before_loop, loop, access_fn); + VEC_safe_push (tree, heap, access_fns, access_fn); - /* Strip conversions that don't narrow the mode. */ - expr = strip_conversion (expr); - if (!expr) - return false; + TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0); + } + + aref = TREE_OPERAND (aref, 0); + } - /* Stop conditions: - 1. Constant. */ - if (TREE_CODE (expr) == INTEGER_CST) + if (INDIRECT_REF_P (aref)) { - *initial_offset = fold_convert (ssizetype, expr); - *misalign = fold_convert (ssizetype, expr); - *step = ssize_int (0); - return true; + op = TREE_OPERAND (aref, 0); + access_fn = analyze_scalar_evolution (loop, op); + access_fn = instantiate_scev (before_loop, loop, access_fn); + base = initial_condition (access_fn); + split_constant_offset (base, &base, &off); + access_fn = chrec_replace_initial_condition (access_fn, + fold_convert (TREE_TYPE (base), off)); + + TREE_OPERAND (aref, 0) = base; + VEC_safe_push (tree, heap, access_fns, access_fn); } - /* 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); + DR_BASE_OBJECT (dr) = ref; + DR_ACCESS_FNS (dr) = access_fns; +} - if (access_fn == chrec_dont_know) - /* No access_fn. */ - return false; +/* Extracts the alias analysis information from the memory reference DR. */ - 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; +static void +dr_analyze_alias (struct data_reference *dr) +{ + gimple stmt = DR_STMT (dr); + tree ref = DR_REF (dr); + tree base = get_base_address (ref), addr, smt = NULL_TREE; + ssa_op_iter it; + tree op; + bitmap vops; + + if (DECL_P (base)) + smt = base; + else if (INDIRECT_REF_P (base)) + { + addr = TREE_OPERAND (base, 0); + if (TREE_CODE (addr) == SSA_NAME) + { + smt = symbol_mem_tag (SSA_NAME_VAR (addr)); + DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr); + } + } - evolution = evolution_part_in_loop_num (access_fn, loop->num); - if (evolution && TREE_CODE (evolution) != INTEGER_CST) - /* Evolution is not constant. */ - return false; + DR_SYMBOL_TAG (dr) = smt; - if (TREE_CODE (init) == INTEGER_CST) - *misalign = fold_convert (ssizetype, init); - else - /* Not constant, misalignment cannot be calculated. */ - *misalign = NULL_TREE; + vops = BITMAP_ALLOC (NULL); + FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES) + { + bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op))); + } - *initial_offset = fold_convert (ssizetype, init); + DR_VOPS (dr) = vops; +} - *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0); - return true; - } +/* Returns true if the address of DR is invariant. */ - /* 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"); - } +static bool +dr_address_invariant_p (struct data_reference *dr) +{ + unsigned i; + tree idx; + + for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++) + if (tree_contains_chrecs (idx, NULL)) 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; + return true; +} - /* 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; +/* Frees data reference DR. */ - /* 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; - } +void +free_data_ref (data_reference_p dr) +{ + BITMAP_FREE (DR_VOPS (dr)); + VEC_free (tree, heap, DR_ACCESS_FNS (dr)); + free (dr); +} - /* 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); +/* Analyzes memory reference MEMREF accessed in STMT. The reference + is read if IS_READ is true, write otherwise. Returns the + data_reference description of MEMREF. NEST is the outermost loop of the + loop nest in that the reference should be analyzed. */ - /* Unknown alignment. */ - if ((!left_misalign && !left_aligned_to) - || (!right_misalign && !right_aligned_to)) - { - *misalign = NULL_TREE; - *aligned_to = NULL_TREE; - break; - } +struct data_reference * +create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read) +{ + struct data_reference *dr; - if (left_misalign && right_misalign) - *misalign = size_binop (code, left_misalign, right_misalign); - else - *misalign = left_misalign ? left_misalign : right_misalign; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Creating dr for "); + print_generic_expr (dump_file, memref, TDF_SLIM); + fprintf (dump_file, "\n"); + } - 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; + dr = XCNEW (struct data_reference); + DR_STMT (dr) = stmt; + DR_REF (dr) = memref; + DR_IS_READ (dr) = is_read; - break; + dr_analyze_innermost (dr); + dr_analyze_indices (dr, nest); + dr_analyze_alias (dr); - default: - gcc_unreachable (); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\tbase_address: "); + print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM); + fprintf (dump_file, "\n\toffset from base address: "); + print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM); + fprintf (dump_file, "\n\tconstant offset from base address: "); + print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM); + fprintf (dump_file, "\n\tstep: "); + print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM); + fprintf (dump_file, "\n\taligned to: "); + print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM); + fprintf (dump_file, "\n\tbase_object: "); + print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); + fprintf (dump_file, "\n\tsymbol tag: "); + print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM); + fprintf (dump_file, "\n"); } - /* Compute offset. */ - *initial_offset = fold_convert (ssizetype, - fold_build2 (code, TREE_TYPE (left_offset), - left_offset, - right_offset)); - return true; + return dr; } -/* Function address_analysis +/* Returns true if FNA == FNB. */ - Return the BASE of the address expression EXPR. - Also compute the OFFSET from BASE, MISALIGN and STEP. +static bool +affine_function_equal_p (affine_fn fna, affine_fn fnb) +{ + unsigned i, n = VEC_length (tree, fna); - 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 + if (n != VEC_length (tree, fnb)) + return false; - 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. - */ + for (i = 0; i < n; i++) + if (!operand_equal_p (VEC_index (tree, fna, i), + VEC_index (tree, fnb, i), 0)) + return false; -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; + return true; +} - 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); +/* If all the functions in CF are the same, returns one of them, + otherwise returns NULL. */ - 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; - } +static affine_fn +common_affine_function (conflict_function *cf) +{ + unsigned i; + affine_fn comm; - /* 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); + if (!CF_NONTRIVIAL_P (cf)) + return NULL; - /* 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; - } + comm = cf->fns[0]; - /* 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; + for (i = 1; i < cf->n; i++) + if (!affine_function_equal_p (comm, cf->fns[i])) + return NULL; - 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; + return comm; +} - 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; - } +/* Returns the base of the affine function FN. */ + +static tree +affine_function_base (affine_fn fn) +{ + return VEC_index (tree, fn, 0); } +/* Returns true if FN is a constant. */ + +static bool +affine_function_constant_p (affine_fn fn) +{ + unsigned i; + tree coef; -/* Function object_analysis + for (i = 1; VEC_iterate (tree, fn, i, coef); i++) + if (!integer_zerop (coef)) + return false; - 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; + return true; +} - *ptr_info = NULL; +/* Returns true if FN is the zero constant function. */ - /* 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 = init_array_ref (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; - } - } +static bool +affine_function_zero_p (affine_fn fn) +{ + return (integer_zerop (affine_function_base (fn)) + && affine_function_constant_p (fn)); +} - /* 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; - } +/* Returns a signed integer type with the largest precision from TA + and TB. */ - /* 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; - } +static tree +signed_type_for_types (tree ta, tree tb) +{ + if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb)) + return signed_type_for (ta); + else + return signed_type_for (tb); +} - /* Add bit position to OFFSET and MISALIGN. */ +/* Applies operation OP on affine functions FNA and FNB, and returns the + result. */ - 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 */ +static affine_fn +affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb) +{ + unsigned i, n, m; + affine_fn ret; + tree coef; + + if (VEC_length (tree, fnb) > VEC_length (tree, fna)) + { + n = VEC_length (tree, fna); + m = VEC_length (tree, fnb); } - - /* Part 1: Case 2. Declarations. */ - if (DECL_P (memref)) + else { - /* 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 = init_array_ref (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; + n = VEC_length (tree, fnb); + m = VEC_length (tree, fna); } - /* Part 1: Case 3. INDIRECT_REFs. */ - else if (TREE_CODE (memref) == INDIRECT_REF) + ret = VEC_alloc (tree, heap, m); + for (i = 0; i < n; i++) { - tree ptr_ref = TREE_OPERAND (memref, 0); - if (TREE_CODE (ptr_ref) == SSA_NAME) - *ptr_info = SSA_NAME_PTR_INFO (ptr_ref); + tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)), + TREE_TYPE (VEC_index (tree, fnb, i))); - /* 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 = symbol_mem_tag (SSA_NAME_VAR (base_address)); - if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME) - *memtag = symbol_mem_tag (SSA_NAME_VAR (TREE_OPERAND (memref, 0))); - 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 if FNA == FNB. */ - -static bool -affine_function_equal_p (affine_fn fna, affine_fn fnb) -{ - unsigned i, n = VEC_length (tree, fna); - - if (n != VEC_length (tree, fnb)) - return false; - - for (i = 0; i < n; i++) - if (!operand_equal_p (VEC_index (tree, fna, i), - VEC_index (tree, fnb, i), 0)) - return false; - - return true; -} - -/* If all the functions in CF are the same, returns one of them, - otherwise returns NULL. */ - -static affine_fn -common_affine_function (conflict_function *cf) -{ - unsigned i; - affine_fn comm; - - if (!CF_NONTRIVIAL_P (cf)) - return NULL; - - comm = cf->fns[0]; - - for (i = 1; i < cf->n; i++) - if (!affine_function_equal_p (comm, cf->fns[i])) - return NULL; - - return comm; -} - -/* Returns the base of the affine function FN. */ - -static tree -affine_function_base (affine_fn fn) -{ - return VEC_index (tree, fn, 0); -} - -/* Returns true if FN is a constant. */ - -static bool -affine_function_constant_p (affine_fn fn) -{ - unsigned i; - tree coef; - - for (i = 1; VEC_iterate (tree, fn, i, coef); i++) - if (!integer_zerop (coef)) - return false; - - return true; -} - -/* Applies operation OP on affine functions FNA and FNB, and returns the - result. */ - -static affine_fn -affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb) -{ - unsigned i, n, m; - affine_fn ret; - tree coef; - - if (VEC_length (tree, fnb) > VEC_length (tree, fna)) - { - n = VEC_length (tree, fna); - m = VEC_length (tree, fnb); - } - else - { - n = VEC_length (tree, fnb); - m = VEC_length (tree, fna); + VEC_quick_push (tree, ret, + fold_build2 (op, type, + VEC_index (tree, fna, i), + VEC_index (tree, fnb, i))); } - ret = VEC_alloc (tree, heap, m); - for (i = 0; i < n; i++) - VEC_quick_push (tree, ret, - fold_build2 (op, integer_type_node, - VEC_index (tree, fna, i), - VEC_index (tree, fnb, i))); - for (; VEC_iterate (tree, fna, i, coef); i++) VEC_quick_push (tree, ret, - fold_build2 (op, integer_type_node, + fold_build2 (op, signed_type_for (TREE_TYPE (coef)), coef, integer_zero_node)); for (; VEC_iterate (tree, fnb, i, coef); i++) VEC_quick_push (tree, ret, - fold_build2 (op, integer_type_node, + fold_build2 (op, signed_type_for (TREE_TYPE (coef)), integer_zero_node, coef)); return ret; @@ -2250,65 +1107,257 @@ conflict_fn_no_dependence (void) return fn; } -/* 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. */ +/* Returns true if the address of OBJ is invariant in LOOP. */ -static struct data_dependence_relation * -initialize_data_dependence_relation (struct data_reference *a, - struct data_reference *b, - VEC (loop_p, heap) *loop_nest) +static bool +object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj) { - 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) + while (handled_component_p (obj)) { - 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 (TREE_CODE (obj) == ARRAY_REF) + { + /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only + need to check the stride and the lower bound of the reference. */ + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2), + loop->num) + || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3), + loop->num)) + return false; + } + else if (TREE_CODE (obj) == COMPONENT_REF) + { + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2), + loop->num)) + return false; + } + obj = TREE_OPERAND (obj, 0); } - if (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 (!INDIRECT_REF_P (obj)) + return true; - if (!known_dependence) - { - /* Can't determine whether the data-refs access the same memory - region. */ - DDR_ARE_DEPENDENT (res) = chrec_dont_know; - return res; + return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0), + loop->num); +} + +/* Returns true if A and B are accesses to different objects, or to different + fields of the same object. */ + +static bool +disjoint_objects_p (tree a, tree b) +{ + tree base_a, base_b; + VEC (tree, heap) *comp_a = NULL, *comp_b = NULL; + bool ret; + + base_a = get_base_address (a); + base_b = get_base_address (b); + + if (DECL_P (base_a) + && DECL_P (base_b) + && base_a != base_b) + return true; + + if (!operand_equal_p (base_a, base_b, 0)) + return false; + + /* Compare the component references of A and B. We must start from the inner + ones, so record them to the vector first. */ + while (handled_component_p (a)) + { + VEC_safe_push (tree, heap, comp_a, a); + a = TREE_OPERAND (a, 0); + } + while (handled_component_p (b)) + { + VEC_safe_push (tree, heap, comp_b, b); + b = TREE_OPERAND (b, 0); + } + + ret = false; + while (1) + { + if (VEC_length (tree, comp_a) == 0 + || VEC_length (tree, comp_b) == 0) + break; + + a = VEC_pop (tree, comp_a); + b = VEC_pop (tree, comp_b); + + /* Real and imaginary part of a variable do not alias. */ + if ((TREE_CODE (a) == REALPART_EXPR + && TREE_CODE (b) == IMAGPART_EXPR) + || (TREE_CODE (a) == IMAGPART_EXPR + && TREE_CODE (b) == REALPART_EXPR)) + { + ret = true; + break; + } + + if (TREE_CODE (a) != TREE_CODE (b)) + break; + + /* Nothing to do for ARRAY_REFs, as the indices of array_refs in + DR_BASE_OBJECT are always zero. */ + if (TREE_CODE (a) == ARRAY_REF) + continue; + else if (TREE_CODE (a) == COMPONENT_REF) + { + if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0)) + continue; + + /* Different fields of unions may overlap. */ + base_a = TREE_OPERAND (a, 0); + if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE) + break; + + /* Different fields of structures cannot. */ + ret = true; + break; + } + else + break; } - if (differ_p) + VEC_free (tree, heap, comp_a); + VEC_free (tree, heap, comp_b); + + return ret; +} + +/* Returns false if we can prove that data references A and B do not alias, + true otherwise. */ + +bool +dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) +{ + const_tree addr_a = DR_BASE_ADDRESS (a); + const_tree addr_b = DR_BASE_ADDRESS (b); + const_tree type_a, type_b; + const_tree decl_a = NULL_TREE, decl_b = NULL_TREE; + + /* If the sets of virtual operands are disjoint, the memory references do not + alias. */ + if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b))) + return false; + + /* If the accessed objects are disjoint, the memory references do not + alias. */ + if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b))) + return false; + + if (!addr_a || !addr_b) + return true; + + /* If the references are based on different static objects, they cannot alias + (PTA should be able to disambiguate such accesses, but often it fails to, + since currently we cannot distinguish between pointer and offset in pointer + arithmetics). */ + if (TREE_CODE (addr_a) == ADDR_EXPR + && TREE_CODE (addr_b) == ADDR_EXPR) + return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0); + + /* An instruction writing through a restricted pointer is "independent" of any + instruction reading or writing through a different restricted pointer, + in the same block/scope. */ + + type_a = TREE_TYPE (addr_a); + type_b = TREE_TYPE (addr_b); + gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b)); + + if (TREE_CODE (addr_a) == SSA_NAME) + decl_a = SSA_NAME_VAR (addr_a); + if (TREE_CODE (addr_b) == SSA_NAME) + decl_b = SSA_NAME_VAR (addr_b); + + if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b) + && (!DR_IS_READ (a) || !DR_IS_READ (b)) + && decl_a && DECL_P (decl_a) + && decl_b && DECL_P (decl_b) + && decl_a != decl_b + && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL + && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b)) + return false; + + return true; +} + +static void compute_self_dependence (struct data_dependence_relation *); + +/* 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; + unsigned int i; + + res = XNEW (struct data_dependence_relation); + DDR_A (res) = a; + DDR_B (res) = b; + DDR_LOOP_NEST (res) = NULL; + DDR_REVERSED_P (res) = false; + DDR_SUBSCRIPTS (res) = NULL; + DDR_DIR_VECTS (res) = NULL; + DDR_DIST_VECTS (res) = NULL; + + if (a == NULL || b == NULL) + { + DDR_ARE_DEPENDENT (res) = chrec_dont_know; + return res; + } + + /* If the data references do not alias, then they are independent. */ + if (!dr_may_alias_p (a, b)) { DDR_ARE_DEPENDENT (res) = chrec_known; return res; } - + + /* When the references are exactly the same, don't spend time doing + the data dependence tests, just initialize the ddr and return. */ + if (operand_equal_p (DR_REF (a), DR_REF (b), 0)) + { + 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_INNER_LOOP (res) = 0; + DDR_SELF_REFERENCE (res) = true; + compute_self_dependence (res); + return res; + } + + /* If the references do not access the same object, we do not know + whether they alias or not. */ + if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0)) + { + DDR_ARE_DEPENDENT (res) = chrec_dont_know; + return res; + } + + /* If the base of the object is not invariant in the loop nest, we cannot + analyze it. TODO -- in fact, it would suffice to record that there may + be arbitrary dependences in the loops where the base object varies. */ + if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0), + DR_BASE_OBJECT (a))) + { + DDR_ARE_DEPENDENT (res) = chrec_dont_know; + return res; + } + + gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)); + 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_INNER_LOOP (res) = 0; - DDR_DIR_VECTS (res) = NULL; - DDR_DIST_VECTS (res) = NULL; + DDR_SELF_REFERENCE (res) = false; for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) { @@ -2352,6 +1401,7 @@ free_subscripts (VEC (subscript_p, heap) *subscripts) { free_conflict_function (s->conflicting_iterations_in_a); free_conflict_function (s->conflicting_iterations_in_b); + free (s); } VEC_free (subscript_p, heap, subscripts); } @@ -2372,6 +1422,7 @@ finalize_ddr_dependent (struct data_dependence_relation *ddr, DDR_ARE_DEPENDENT (ddr) = chrec; free_subscripts (DDR_SUBSCRIPTS (ddr)); + DDR_SUBSCRIPTS (ddr) = NULL; } /* The dependence relation DDR cannot be represented by a distance @@ -2394,8 +1445,7 @@ non_affine_dependence_relation (struct data_dependence_relation *ddr) variables, i.e., if the ZIV (Zero Index Variable) test is true. */ static inline bool -ziv_subscript_p (tree chrec_a, - tree chrec_b) +ziv_subscript_p (const_tree chrec_a, const_tree chrec_b) { return (evolution_function_is_constant_p (chrec_a) && evolution_function_is_constant_p (chrec_b)); @@ -2405,8 +1455,7 @@ ziv_subscript_p (tree chrec_a, variable, i.e., if the SIV (Single Index Variable) test is true. */ static bool -siv_subscript_p (tree chrec_a, - tree chrec_b) +siv_subscript_p (const_tree chrec_a, const_tree chrec_b) { if ((evolution_function_is_constant_p (chrec_a) && evolution_function_is_univariate_p (chrec_b)) @@ -2499,15 +1548,16 @@ analyze_ziv_subscript (tree chrec_a, conflict_function **overlaps_b, tree *last_conflicts) { - tree difference; + tree type, 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); + + type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b)); + chrec_a = chrec_convert (type, chrec_a, NULL); + chrec_b = chrec_convert (type, chrec_b, NULL); + difference = chrec_fold_minus (type, chrec_a, chrec_b); switch (TREE_CODE (difference)) { @@ -2633,12 +1683,12 @@ analyze_siv_subscript_cst_affine (tree chrec_a, tree *last_conflicts) { bool value0, value1, value2; - tree difference, tmp; + tree type, difference, tmp; - 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); + type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b)); + chrec_a = chrec_convert (type, chrec_a, NULL); + chrec_b = chrec_convert (type, chrec_b, NULL); + difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a); if (!chrec_is_positive (initial_condition (difference), &value0)) { @@ -2681,10 +1731,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, struct loop *loop = get_chrec_loop (chrec_b); *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); - tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node, - fold_build1 (ABS_EXPR, - integer_type_node, - difference), + tmp = fold_build2 (EXACT_DIV_EXPR, type, + fold_build1 (ABS_EXPR, type, difference), CHREC_RIGHT (chrec_b)); *overlaps_b = conflict_fn (1, affine_fn_cst (tmp)); *last_conflicts = integer_one_node; @@ -2692,7 +1740,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Perform weak-zero siv test to see if overlap is outside the loop bounds. */ - numiter = estimated_loop_iterations_int (loop, true); + numiter = estimated_loop_iterations_int (loop, false); if (numiter >= 0 && compare_tree_int (tmp, numiter) > 0) @@ -2763,15 +1811,14 @@ analyze_siv_subscript_cst_affine (tree chrec_a, struct loop *loop = get_chrec_loop (chrec_b); *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); - tmp = fold_build2 (EXACT_DIV_EXPR, - integer_type_node, difference, + tmp = fold_build2 (EXACT_DIV_EXPR, type, difference, CHREC_RIGHT (chrec_b)); *overlaps_b = conflict_fn (1, affine_fn_cst (tmp)); *last_conflicts = integer_one_node; /* Perform weak-zero siv test to see if overlap is outside the loop bounds. */ - numiter = estimated_loop_iterations_int (loop, true); + numiter = estimated_loop_iterations_int (loop, false); if (numiter >= 0 && compare_tree_int (tmp, numiter) > 0) @@ -2820,16 +1867,42 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Helper recursive function for initializing the matrix A. Returns the initial value of CHREC. */ -static int +static tree 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); + switch (TREE_CODE (chrec)) + { + case POLYNOMIAL_CHREC: + gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST); + + A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); + return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); + + case PLUS_EXPR: + case MULT_EXPR: + case MINUS_EXPR: + { + tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult); + tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult); + + return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1); + } + + case NOP_EXPR: + { + tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult); + return chrec_convert (chrec_type (chrec), op, NULL); + } + + case INTEGER_CST: + return chrec; - A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); - return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); + default: + gcc_unreachable (); + return NULL_TREE; + } } #define FLOOR_DIV(x,y) ((x) / (y)) @@ -2857,9 +1930,15 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int 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; + if (niter > 0) + { + tau2 = FLOOR_DIV (niter, step_overlaps_a); + tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); + last_conflict = tau2; + *last_conflicts = build_int_cst (NULL_TREE, last_conflict); + } + else + *last_conflicts = chrec_dont_know; *overlaps_a = affine_fn_univar (integer_zero_node, dim, build_int_cst (NULL_TREE, @@ -2867,7 +1946,6 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, *overlaps_b = affine_fn_univar (integer_zero_node, dim, build_int_cst (NULL_TREE, step_overlaps_b)); - *last_conflicts = build_int_cst (NULL_TREE, last_conflict); } else @@ -2912,10 +1990,11 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, step_y = int_cst_value (CHREC_RIGHT (chrec_a)); step_z = int_cst_value (CHREC_RIGHT (chrec_b)); - niter_x = estimated_loop_iterations_int - (get_chrec_loop (CHREC_LEFT (chrec_a)), true); - niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true); - niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true); + niter_x = + estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)), + false); + niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false); + niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false); if (niter_x < 0 || niter_y < 0 || niter_z < 0) { @@ -3021,8 +2100,7 @@ analyze_subscript_affine_affine (tree chrec_a, tree *last_conflicts) { unsigned nb_vars_a, nb_vars_b, dim; - int init_a, init_b, gamma, gcd_alpha_beta; - int tau1, tau2; + HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta; lambda_matrix A, U, S; if (eq_evolutions_p (chrec_a, chrec_b)) @@ -3056,8 +2134,8 @@ analyze_subscript_affine_affine (tree chrec_a, 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); + init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1)); + init_b = int_cst_value (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 @@ -3072,26 +2150,15 @@ analyze_subscript_affine_affine (tree chrec_a, { if (nb_vars_a == 1 && nb_vars_b == 1) { - int step_a, step_b; + HOST_WIDE_INT step_a, step_b; HOST_WIDE_INT niter, niter_a, niter_b; affine_fn ova, ovb; - niter_a = estimated_loop_iterations_int - (get_chrec_loop (chrec_a), true); - niter_b = estimated_loop_iterations_int - (get_chrec_loop (chrec_b), true); - if (niter_a < 0 || niter_b < 0) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); - *overlaps_a = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); - *last_conflicts = chrec_dont_know; - goto end_analyze_subs_aa; - } - + niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a), + false); + niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b), + false); niter = MIN (niter_a, niter_b); - step_a = int_cst_value (CHREC_RIGHT (chrec_a)); step_b = int_cst_value (CHREC_RIGHT (chrec_b)); @@ -3175,31 +2242,7 @@ analyze_subscript_affine_affine (tree chrec_a, | 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; - - niter_a = estimated_loop_iterations_int - (get_chrec_loop (chrec_a), true); - niter_b = estimated_loop_iterations_int - (get_chrec_loop (chrec_b), true); - - if (niter_a < 0 || niter_b < 0) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); - *overlaps_a = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); - *last_conflicts = chrec_dont_know; - goto end_analyze_subs_aa; - } - - niter = MIN (niter_a, niter_b); + HOST_WIDE_INT i0, j0, i1, j1; i0 = U[0][0] * gamma / gcd_alpha_beta; j0 = U[0][1] * gamma / gcd_alpha_beta; @@ -3216,80 +2259,72 @@ analyze_subscript_affine_affine (tree chrec_a, *overlaps_a = conflict_fn_no_dependence (); *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; + goto end_analyze_subs_aa; } - else + if (i1 > 0 && j1 > 0) { - if (i1 > 0) + HOST_WIDE_INT niter_a = estimated_loop_iterations_int + (get_chrec_loop (chrec_a), false); + HOST_WIDE_INT niter_b = estimated_loop_iterations_int + (get_chrec_loop (chrec_b), false); + HOST_WIDE_INT niter = MIN (niter_a, niter_b); + + /* (X0, Y0) is a solution of the Diophantine equation: + "chrec_a (X0) = chrec_b (Y0)". */ + HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1), + CEIL (-j0, j1)); + HOST_WIDE_INT x0 = i1 * tau1 + i0; + HOST_WIDE_INT y0 = j1 * tau1 + j0; + + /* (X1, Y1) is the smallest positive solution of the eq + "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the + first conflict occurs. */ + HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1); + HOST_WIDE_INT x1 = x0 - i1 * min_multiple; + HOST_WIDE_INT y1 = y0 - j1 * min_multiple; + + if (niter > 0) { - tau1 = CEIL (-i0, i1); - tau2 = FLOOR_DIV (niter - i0, i1); + HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1), + FLOOR_DIV (niter - j0, j1)); + HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1; - if (j1 > 0) + /* If the overlap occurs outside of the bounds of the + loop, there is no dependence. */ + if (x1 > niter || y1 > niter) { - 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 = conflict_fn_no_dependence (); - *overlaps_b = conflict_fn_no_dependence (); - *last_conflicts = integer_zero_node; - } - else - { - *overlaps_a - = conflict_fn (1, - affine_fn_univar (build_int_cst (NULL_TREE, x0), - 1, - build_int_cst (NULL_TREE, i1))); - *overlaps_b - = conflict_fn (1, - affine_fn_univar (build_int_cst (NULL_TREE, y0), - 1, - build_int_cst (NULL_TREE, j1))); - *last_conflicts = build_int_cst (NULL_TREE, last_conflict); - } + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + goto end_analyze_subs_aa; } 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 = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); - *last_conflicts = chrec_dont_know; - } + *last_conflicts = build_int_cst (NULL_TREE, last_conflict); } - 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 = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); - *last_conflicts = chrec_dont_know; - } + *last_conflicts = chrec_dont_know; + + *overlaps_a + = conflict_fn (1, + affine_fn_univar (build_int_cst (NULL_TREE, x1), + 1, + build_int_cst (NULL_TREE, i1))); + *overlaps_b + = conflict_fn (1, + affine_fn_univar (build_int_cst (NULL_TREE, y1), + 1, + build_int_cst (NULL_TREE, j1))); + } + else + { + /* FIXME: For the moment, the upper bound of the + iteration domain for i and j is not checked. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; } } else @@ -3301,7 +2336,6 @@ analyze_subscript_affine_affine (tree chrec_a, *last_conflicts = chrec_dont_know; } } - else { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -3349,7 +2383,7 @@ can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) type = chrec_type (*chrec_a); left_a = CHREC_LEFT (*chrec_a); - left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE); + left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL); diff = chrec_fold_minus (type, left_a, left_b); if (!evolution_function_is_constant_p (diff)) @@ -3360,7 +2394,7 @@ can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) *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); + right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL); *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b), build_int_cst (type, 0), right_b); @@ -3379,7 +2413,8 @@ analyze_siv_subscript (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, - tree *last_conflicts) + tree *last_conflicts, + int loop_nest_num) { dependence_stats.num_siv++; @@ -3387,17 +2422,17 @@ analyze_siv_subscript (tree chrec_a, fprintf (dump_file, "(analyze_siv_subscript \n"); if (evolution_function_is_constant_p (chrec_a) - && evolution_function_is_affine_p (chrec_b)) + && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num)) analyze_siv_subscript_cst_affine (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); - else if (evolution_function_is_affine_p (chrec_a) + else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num) && 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)) + else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num) + && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num)) { if (!chrec_contains_symbols (chrec_a) && !chrec_contains_symbols (chrec_b)) @@ -3421,9 +2456,6 @@ analyze_siv_subscript (tree chrec_a, 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 (CF_NOT_KNOWN_P (*overlaps_a) || CF_NOT_KNOWN_P (*overlaps_b)) @@ -3453,42 +2485,36 @@ analyze_siv_subscript (tree chrec_a, 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. */ +/* Returns false if we can prove that the greatest common divisor of the steps + of CHREC does not divide CST, false otherwise. */ static bool -chrec_steps_divide_constant_p (tree chrec, - tree cst, - bool *res) +gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst) { - 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; + HOST_WIDE_INT cd = 0, val; + tree step; - default: - /* On the initial condition, return true. */ - return true; + if (!host_integerp (cst, 0)) + return true; + val = tree_low_cst (cst, 0); + + while (TREE_CODE (chrec) == POLYNOMIAL_CHREC) + { + step = CHREC_RIGHT (chrec); + if (!host_integerp (step, 0)) + return true; + cd = gcd (cd, tree_low_cst (step, 0)); + chrec = CHREC_LEFT (chrec); } + + return val % cd == 0; } -/* 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: +/* Analyze a MIV (Multiple Index Variable) subscript with respect to + LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the + functions that describe the relation between the elements accessed + twice by CHREC_A and CHREC_B. For k >= 0, the following property + is verified: CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ @@ -3497,7 +2523,8 @@ analyze_miv_subscript (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, - tree *last_conflicts) + tree *last_conflicts, + struct loop *loop_nest) { /* FIXME: This is a MIV subscript, not yet handled. Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from @@ -3507,15 +2534,16 @@ analyze_miv_subscript (tree chrec_a, 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; + tree type, 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); + type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b)); + chrec_a = chrec_convert (type, chrec_a, NULL); + chrec_b = chrec_convert (type, chrec_b, NULL); + difference = chrec_fold_minus (type, chrec_a, chrec_b); if (eq_evolutions_p (chrec_a, chrec_b)) { @@ -3530,24 +2558,24 @@ analyze_miv_subscript (tree chrec_a, 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, ÷_p) - && !divide_p) + evolution_function_is_affine_multivariate_p (chrec_a, + loop_nest->num) */ + && !gcd_of_steps_may_divide_p (chrec_a, difference)) { /* testsuite/.../ssa-chrec-33.c {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 - The difference is 1, and the evolution steps are equal to 2, - consequently there are no overlapping elements. */ + The difference is 1, and all the evolution steps are multiples + of 2, consequently there are no overlapping elements. */ *overlaps_a = conflict_fn_no_dependence (); *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_miv_independent++; } - else if (evolution_function_is_affine_multivariate_p (chrec_a) + else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num) && !chrec_contains_symbols (chrec_a) - && evolution_function_is_affine_multivariate_p (chrec_b) + && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num) && !chrec_contains_symbols (chrec_b)) { /* testsuite/.../ssa-chrec-35.c @@ -3593,10 +2621,10 @@ analyze_miv_subscript (tree chrec_a, 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. +/* Determines the iterations for which CHREC_A is equal to CHREC_B in + with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and + OVERLAP_ITERATIONS_B are initialized with two functions that + describe the iterations that contain conflicting elements. Remark: For an integer k >= 0, the following equality is true: @@ -3608,8 +2636,10 @@ analyze_overlapping_iterations (tree chrec_a, tree chrec_b, conflict_function **overlap_iterations_a, conflict_function **overlap_iterations_b, - tree *last_conflicts) + tree *last_conflicts, struct loop *loop_nest) { + unsigned int lnn = loop_nest->num; + dependence_stats.num_subscript_tests++; if (dump_file && (dump_flags & TDF_DETAILS)) @@ -3636,7 +2666,7 @@ analyze_overlapping_iterations (tree chrec_a, /* 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)) + && evolution_function_is_affine_multivariate_p (chrec_a, lnn)) { dependence_stats.num_same_subscript_function++; *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); @@ -3648,8 +2678,8 @@ analyze_overlapping_iterations (tree chrec_a, 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))) + && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn) + || !evolution_function_is_affine_multivariate_p (chrec_b, lnn))) { dependence_stats.num_subscript_undetermined++; *overlap_iterations_a = conflict_fn_not_known (); @@ -3664,12 +2694,12 @@ analyze_overlapping_iterations (tree chrec_a, else if (siv_subscript_p (chrec_a, chrec_b)) analyze_siv_subscript (chrec_a, chrec_b, overlap_iterations_a, overlap_iterations_b, - last_conflicts); + last_conflicts, lnn); else analyze_miv_subscript (chrec_a, chrec_b, overlap_iterations_a, overlap_iterations_b, - last_conflicts); + last_conflicts, loop_nest); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -3818,7 +2848,7 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr, init_v[index] = 1; *init_b = true; } - else + else if (!operand_equal_p (access_fn_a, access_fn_b, 0)) { /* This can be for example an affine vs. constant dependence (T[i] vs. T[3]) that is not an affine dependence and is @@ -3831,24 +2861,24 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr, return true; } -/* Return true when the DDR contains two data references that have the - same access functions. */ +/* Return true when the DDR contains only constant access functions. */ static bool -same_access_functions (struct data_dependence_relation *ddr) +constant_access_functions (const 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))) + if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i)) + || !evolution_function_is_constant_p (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. */ + multivariate access function with a constant step. For an example + see pr34635-1.c. */ static void add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2) @@ -3857,11 +2887,16 @@ add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_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) + int v1, v2, cd; + + /* Polynomials with more than 2 variables are not handled yet. When + the evolution steps are parameters, it is not possible to + represent the dependence using classical distance vectors. */ + if (TREE_CODE (c_0) != INTEGER_CST + || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST + || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST) { - DDR_ARE_DEPENDENT (ddr) = chrec_dont_know; + DDR_AFFINE_P (ddr) = false; return; } @@ -3870,8 +2905,20 @@ add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2) /* 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)); + v1 = int_cst_value (CHREC_RIGHT (c_1)); + v2 = int_cst_value (CHREC_RIGHT (c_2)); + cd = gcd (v1, v2); + v1 /= cd; + v2 /= cd; + + if (v2 < 0) + { + v2 = -v2; + v1 = -v1; + } + + dist_v[x_1] = v2; + dist_v[x_2] = -v1; save_dist_v (ddr, dist_v); add_outer_distances (ddr, dist_v, x_1); @@ -3901,7 +2948,17 @@ add_other_self_distances (struct data_dependence_relation *ddr) return; } - add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0)); + access_fun = DR_ACCESS_FN (DDR_A (ddr), 0); + + if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC) + add_multivariate_self_dist (ddr, access_fun); + else + /* The evolution step is not constant: it varies in + the outer loop, so this cannot be represented by a + distance vector. For example in pr34635.c the + evolution is {0, +, {0, +, 4}_1}_2. */ + DDR_AFFINE_P (ddr) = false; + return; } @@ -3915,19 +2972,67 @@ add_other_self_distances (struct data_dependence_relation *ddr) add_outer_distances (ddr, dist_v, index_carry); } +static void +insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr) +{ + lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + + dist_v[DDR_INNER_LOOP (ddr)] = 1; + save_dist_v (ddr, dist_v); +} + +/* Adds a unit distance vector to DDR when there is a 0 overlap. This + is the case for example when access functions are the same and + equal to a constant, as in: + + | loop_1 + | A[3] = ... + | ... = A[3] + | endloop_1 + + in which case the distance vectors are (0) and (1). */ + +static void +add_distance_for_zero_overlaps (struct data_dependence_relation *ddr) +{ + unsigned i, j; + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + subscript_p sub = DDR_SUBSCRIPT (ddr, i); + conflict_function *ca = SUB_CONFLICTS_IN_A (sub); + conflict_function *cb = SUB_CONFLICTS_IN_B (sub); + + for (j = 0; j < ca->n; j++) + if (affine_function_zero_p (ca->fns[j])) + { + insert_innermost_unit_dist_vector (ddr); + return; + } + + for (j = 0; j < cb->n; j++) + if (affine_function_zero_p (cb->fns[j])) + { + insert_innermost_unit_dist_vector (ddr); + return; + } + } +} + /* 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) +build_classic_dist_vector (struct data_dependence_relation *ddr, + struct loop *loop_nest) { bool init_b = false; int index_carry = DDR_NB_LOOPS (ddr); lambda_vector dist_v; if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) - return true; + return false; if (same_access_functions (ddr)) { @@ -3935,6 +3040,9 @@ build_classic_dist_vector (struct data_dependence_relation *ddr) dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); save_dist_v (ddr, dist_v); + if (constant_access_functions (ddr)) + add_distance_for_zero_overlaps (ddr); + if (DDR_NB_LOOPS (ddr) > 1) add_other_self_distances (ddr); @@ -3976,11 +3084,15 @@ build_classic_dist_vector (struct data_dependence_relation *ddr) 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)); + if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr), + loop_nest)) + return false; compute_subscript_distance (ddr); - build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), - save_v, &init_b, &index_carry); + if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), + save_v, &init_b, &index_carry)) + return false; save_dist_v (ddr, save_v); + DDR_REVERSED_P (ddr) = true; /* In this case there is a dependence forward for all the outer loops: @@ -4008,20 +3120,26 @@ build_classic_dist_vector (struct data_dependence_relation *ddr) { 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)); + if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), + DDR_A (ddr), loop_nest)) + return false; compute_subscript_distance (ddr); - build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), - opposite_v, &init_b, &index_carry); + if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), + opposite_v, &init_b, + &index_carry)) + return false; + save_dist_v (ddr, save_v); add_outer_distances (ddr, dist_v, index_carry); add_outer_distances (ddr, opposite_v, index_carry); } + else + save_dist_v (ddr, save_v); } } else @@ -4097,7 +3215,8 @@ build_classic_dir_vector (struct data_dependence_relation *ddr) static bool subscript_dependence_tester_1 (struct data_dependence_relation *ddr, struct data_reference *dra, - struct data_reference *drb) + struct data_reference *drb, + struct loop *loop_nest) { unsigned int i; tree last_conflicts; @@ -4111,7 +3230,7 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr, analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i), &overlaps_a, &overlaps_b, - &last_conflicts); + &last_conflicts, loop_nest); if (CF_NOT_KNOWN_P (overlaps_a) || CF_NOT_KNOWN_P (overlaps_b)) @@ -4135,6 +3254,11 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr, else { + if (SUB_CONFLICTS_IN_A (subscript)) + free_conflict_function (SUB_CONFLICTS_IN_A (subscript)); + if (SUB_CONFLICTS_IN_B (subscript)) + free_conflict_function (SUB_CONFLICTS_IN_B (subscript)); + SUB_CONFLICTS_IN_A (subscript) = overlaps_a; SUB_CONFLICTS_IN_B (subscript) = overlaps_b; SUB_LAST_CONFLICT (subscript) = last_conflicts; @@ -4144,20 +3268,21 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr, return true; } -/* Computes the conflicting iterations, and initialize DDR. */ +/* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */ static void -subscript_dependence_tester (struct data_dependence_relation *ddr) +subscript_dependence_tester (struct data_dependence_relation *ddr, + struct loop *loop_nest) { 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))) + if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest)) dependence_stats.num_dependence_dependent++; compute_subscript_distance (ddr); - if (build_classic_dist_vector (ddr)) + if (build_classic_dist_vector (ddr, loop_nest)) build_classic_dir_vector (ddr); if (dump_file && (dump_flags & TDF_DETAILS)) @@ -4165,23 +3290,40 @@ subscript_dependence_tester (struct data_dependence_relation *ddr) } /* Returns true when all the access functions of A are affine or - constant. */ + constant with respect to LOOP_NEST. */ static bool -access_functions_are_affine_or_constant_p (struct data_reference *a) +access_functions_are_affine_or_constant_p (const struct data_reference *a, + const struct loop *loop_nest) { unsigned int i; VEC(tree,heap) *fns = DR_ACCESS_FNS (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)) + if (!evolution_function_is_invariant_p (t, loop_nest->num) + && !evolution_function_is_affine_multivariate_p (t, loop_nest->num)) return false; return true; } +/* Return true if we can create an affine data-ref for OP in STMT. */ + +bool +stmt_simple_memref_p (struct loop *loop, gimple stmt, tree op) +{ + data_reference_p dr; + bool res = true; + + dr = create_data_ref (loop, op, stmt, true); + if (!access_functions_are_affine_or_constant_p (dr, loop)) + res = false; + + free_data_ref (dr); + return res; +} + /* Initializes an equation for an OMEGA problem using the information contained in the ACCESS_FUN. Returns true when the operation succeeded. @@ -4364,9 +3506,11 @@ omega_setup_subscript (tree access_fun_a, tree access_fun_b, omega_pb pb, bool *maybe_dependent) { int eq; - tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE); - tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE); - tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b); + tree type = signed_type_for_types (TREE_TYPE (access_fun_a), + TREE_TYPE (access_fun_b)); + tree fun_a = chrec_convert (type, access_fun_a, NULL); + tree fun_b = chrec_convert (type, access_fun_b, NULL); + tree difference = chrec_fold_minus (type, fun_a, fun_b); /* When the fun_a - fun_b is not constant, the dependence is not captured by the classic distance vector representation. */ @@ -4381,8 +3525,7 @@ omega_setup_subscript (tree access_fun_a, tree access_fun_b, return true; } - fun_b = chrec_fold_multiply (integer_type_node, fun_b, - integer_minus_one_node); + fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node); eq = omega_add_zero_eq (pb, omega_black); if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr) @@ -4445,7 +3588,7 @@ init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb, for (i = 0; i <= DDR_INNER_LOOP (ddr) && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++) { - HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, true); + HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false); /* 0 <= loop_x */ ineq = omega_add_zero_geq (pb, omega_black); @@ -4703,598 +3846,1268 @@ ddr_consistent_p (FILE *file, } } - return true; + return true; +} + +/* This computes the affine dependence relation between A and B with + respect to LOOP_NEST. CHREC_KNOWN is used for representing the + independence between two accesses, while CHREC_DONT_KNOW is used + for representing the unknown relation. + + Note that it is possible to stop the computation of the dependence + relation the first time we detect a CHREC_KNOWN element for a given + subscript. */ + +static void +compute_affine_dependence (struct data_dependence_relation *ddr, + struct loop *loop_nest) +{ + 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_gimple_stmt (dump_file, DR_STMT (dra), 0, 0); + fprintf (dump_file, ")\n (stmt_b = \n"); + print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0); + fprintf (dump_file, ")\n"); + } + + /* Analyze only when the dependence relation is not yet known. */ + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE + && !DDR_SELF_REFERENCE (ddr)) + { + dependence_stats.num_dependence_tests++; + + if (access_functions_are_affine_or_constant_p (dra, loop_nest) + && access_functions_are_affine_or_constant_p (drb, loop_nest)) + { + if (flag_check_data_deps) + { + /* Compute the dependences using the first algorithm. */ + subscript_dependence_tester (ddr, loop_nest); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\n\nBanerjee Analyzer\n"); + dump_data_dependence_relation (dump_file, ddr); + } + + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + { + bool maybe_dependent; + VEC (lambda_vector, heap) *dir_vects, *dist_vects; + + /* Save the result of the first DD analyzer. */ + dist_vects = DDR_DIST_VECTS (ddr); + dir_vects = DDR_DIR_VECTS (ddr); + + /* Reset the information. */ + DDR_DIST_VECTS (ddr) = NULL; + DDR_DIR_VECTS (ddr) = NULL; + + /* Compute the same information using Omega. */ + if (!init_omega_for_ddr (ddr, &maybe_dependent)) + goto csys_dont_know; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Omega Analyzer\n"); + dump_data_dependence_relation (dump_file, ddr); + } + + /* Check that we get the same information. */ + if (maybe_dependent) + gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects, + dir_vects)); + } + } + else + subscript_dependence_tester (ddr, loop_nest); + } + + /* 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 + { + csys_dont_know:; + 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; + + if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) + return; + + for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript); + i++) + { + if (SUB_CONFLICTS_IN_A (subscript)) + free_conflict_function (SUB_CONFLICTS_IN_A (subscript)); + if (SUB_CONFLICTS_IN_B (subscript)) + free_conflict_function (SUB_CONFLICTS_IN_B (subscript)); + + /* The accessed index overlaps for each iteration. */ + SUB_CONFLICTS_IN_A (subscript) + = conflict_fn (1, affine_fn_cst (integer_zero_node)); + SUB_CONFLICTS_IN_B (subscript) + = conflict_fn (1, affine_fn_cst (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. */ + +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, VEC_index (loop_p, loop_nest, 0)); + } + + 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); + } +} + +/* Stores the locations of memory references in STMT to REFERENCES. Returns + true if STMT clobbers memory, false otherwise. */ + +bool +get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references) +{ + bool clobbers_memory = false; + data_ref_loc *ref; + tree *op0, *op1; + enum gimple_code stmt_code = gimple_code (stmt); + + *references = NULL; + + /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects. + Calls have side-effects, except those to const or pure + functions. */ + if ((stmt_code == GIMPLE_CALL + && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))) + || (stmt_code == GIMPLE_ASM + && gimple_asm_volatile_p (stmt))) + clobbers_memory = true; + + if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) + return clobbers_memory; + + if (stmt_code == GIMPLE_ASSIGN) + { + tree base; + op0 = gimple_assign_lhs_ptr (stmt); + op1 = gimple_assign_rhs1_ptr (stmt); + + if (DECL_P (*op1) + || (REFERENCE_CLASS_P (*op1) + && (base = get_base_address (*op1)) + && TREE_CODE (base) != SSA_NAME)) + { + ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); + ref->pos = op1; + ref->is_read = true; + } + + if (DECL_P (*op0) + || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))) + { + ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); + ref->pos = op0; + ref->is_read = false; + } + } + else if (stmt_code == GIMPLE_CALL) + { + unsigned i, n = gimple_call_num_args (stmt); + + for (i = 0; i < n; i++) + { + op0 = gimple_call_arg_ptr (stmt, i); + + if (DECL_P (*op0) + || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))) + { + ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); + ref->pos = op0; + ref->is_read = true; + } + } + } + + return clobbers_memory; +} + +/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable + reference, returns false, otherwise returns true. NEST is the outermost + loop of the loop nest in which the references should be analyzed. */ + +bool +find_data_references_in_stmt (struct loop *nest, gimple stmt, + VEC (data_reference_p, heap) **datarefs) +{ + unsigned i; + VEC (data_ref_loc, heap) *references; + data_ref_loc *ref; + bool ret = true; + data_reference_p dr; + + if (get_references_in_stmt (stmt, &references)) + { + VEC_free (data_ref_loc, heap, references); + return false; + } + + for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++) + { + dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read); + gcc_assert (dr != NULL); + + /* FIXME -- data dependence analysis does not work correctly for objects with + invariant addresses. Let us fail here until the problem is fixed. */ + if (dr_address_invariant_p (dr)) + { + free_data_ref (dr); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\tFAILED as dr address is invariant\n"); + ret = false; + break; + } + + VEC_safe_push (data_reference_p, heap, *datarefs, dr); + } + VEC_free (data_ref_loc, heap, references); + return ret; +} + +/* 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; + gimple_stmt_iterator bsi; + + bbs = get_loop_body_in_dom_order (loop); + + for (i = 0; i < loop->num_nodes; i++) + { + bb = bbs[i]; + + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + gimple stmt = gsi_stmt (bsi); + + if (!find_data_references_in_stmt (loop, stmt, datarefs)) + { + struct data_reference *res; + res = XCNEW (struct data_reference); + VEC_safe_push (data_reference_p, heap, *datarefs, res); + + free (bbs); + return chrec_dont_know; + } + } + } + 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. */ + +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; +} + +/* Returns true when the data dependences have been computed, false otherwise. + Given a loop nest LOOP, the following vectors are returned: + DATAREFS is initialized to all the array elements contained in this loop, + DEPENDENCE_RELATIONS contains the relations between the data references. + Compute read-read and self relations if + COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */ + +bool +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) +{ + bool res = true; + 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 + || !find_loop_nest (loop, &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); + res = false; + } + 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); + } + + return res; +} + +/* Entry point (for testing only). Analyze all the data references + and the dependence relations in LOOP. + + 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. */ +static void +analyze_all_data_dependences (struct loop *loop) +{ + 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 (loop, 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); + + if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b))) + 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); +} + +/* Computes all the data dependences and check that the results of + several analyzers are the same. */ + +void +tree_check_data_deps (void) +{ + loop_iterator li; + struct loop *loop_nest; + + FOR_EACH_LOOP (li, loop_nest, 0) + analyze_all_data_dependences (loop_nest); +} + +/* 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_SUBSCRIPTS (ddr)) + free_subscripts (DDR_SUBSCRIPTS (ddr)); + if (DDR_DIST_VECTS (ddr)) + VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr)); + if (DDR_DIR_VECTS (ddr)) + VEC_free (lambda_vector, heap, DDR_DIR_VECTS (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); +} + + + +/* Dump vertex I in RDG to FILE. */ + +void +dump_rdg_vertex (FILE *file, struct graph *rdg, int i) +{ + struct vertex *v = &(rdg->vertices[i]); + struct graph_edge *e; + + fprintf (file, "(vertex %d: (%s%s) (in:", i, + RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "", + RDG_MEM_READS_STMT (rdg, i) ? "r" : ""); + + if (v->pred) + for (e = v->pred; e; e = e->pred_next) + fprintf (file, " %d", e->src); + + fprintf (file, ") (out:"); + + if (v->succ) + for (e = v->succ; e; e = e->succ_next) + fprintf (file, " %d", e->dest); + + fprintf (file, ") \n"); + print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS); + fprintf (file, ")\n"); +} + +/* Call dump_rdg_vertex on stderr. */ + +void +debug_rdg_vertex (struct graph *rdg, int i) +{ + dump_rdg_vertex (stderr, rdg, i); +} + +/* Dump component C of RDG to FILE. If DUMPED is non-null, set the + dumped vertices to that bitmap. */ + +void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped) +{ + int i; + + fprintf (file, "(%d\n", c); + + for (i = 0; i < rdg->n_vertices; i++) + if (rdg->vertices[i].component == c) + { + if (dumped) + bitmap_set_bit (dumped, i); + + dump_rdg_vertex (file, rdg, i); + } + + fprintf (file, ")\n"); +} + +/* Call dump_rdg_vertex on stderr. */ + +void +debug_rdg_component (struct graph *rdg, int c) +{ + dump_rdg_component (stderr, rdg, c, NULL); +} + +/* Dump the reduced dependence graph RDG to FILE. */ + +void +dump_rdg (FILE *file, struct graph *rdg) +{ + int i; + bitmap dumped = BITMAP_ALLOC (NULL); + + fprintf (file, "(rdg\n"); + + for (i = 0; i < rdg->n_vertices; i++) + if (!bitmap_bit_p (dumped, i)) + dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped); + + fprintf (file, ")\n"); + BITMAP_FREE (dumped); +} + +/* Call dump_rdg on stderr. */ + +void +debug_rdg (struct graph *rdg) +{ + dump_rdg (stderr, rdg); +} + +static void +dot_rdg_1 (FILE *file, struct graph *rdg) +{ + int i; + + fprintf (file, "digraph RDG {\n"); + + for (i = 0; i < rdg->n_vertices; i++) + { + struct vertex *v = &(rdg->vertices[i]); + struct graph_edge *e; + + /* Highlight reads from memory. */ + if (RDG_MEM_READS_STMT (rdg, i)) + fprintf (file, "%d [style=filled, fillcolor=green]\n", i); + + /* Highlight stores to memory. */ + if (RDG_MEM_WRITE_STMT (rdg, i)) + fprintf (file, "%d [style=filled, fillcolor=red]\n", i); + + if (v->succ) + for (e = v->succ; e; e = e->succ_next) + switch (RDGE_TYPE (e)) + { + case input_dd: + fprintf (file, "%d -> %d [label=input] \n", i, e->dest); + break; + + case output_dd: + fprintf (file, "%d -> %d [label=output] \n", i, e->dest); + break; + + case flow_dd: + /* These are the most common dependences: don't print these. */ + fprintf (file, "%d -> %d \n", i, e->dest); + break; + + case anti_dd: + fprintf (file, "%d -> %d [label=anti] \n", i, e->dest); + break; + + default: + gcc_unreachable (); + } + } + + fprintf (file, "}\n\n"); } -/* 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. */ +/* Display SCOP using dotty. */ -static void -compute_affine_dependence (struct data_dependence_relation *ddr) +void +dot_rdg (struct graph *rdg) { - 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"); - } + FILE *file = fopen ("/tmp/rdg.dot", "w"); + gcc_assert (file != NULL); - /* Analyze only when the dependence relation is not yet known. */ - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) - { - dependence_stats.num_dependence_tests++; + dot_rdg_1 (file, rdg); + fclose (file); - if (access_functions_are_affine_or_constant_p (dra) - && access_functions_are_affine_or_constant_p (drb)) - { - if (flag_check_data_deps) - { - /* Compute the dependences using the first algorithm. */ - subscript_dependence_tester (ddr); + system ("dotty /tmp/rdg.dot"); +} - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\n\nBanerjee Analyzer\n"); - dump_data_dependence_relation (dump_file, ddr); - } - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) - { - bool maybe_dependent; - VEC (lambda_vector, heap) *dir_vects, *dist_vects; +/* This structure is used for recording the mapping statement index in + the RDG. */ - /* Save the result of the first DD analyzer. */ - dist_vects = DDR_DIST_VECTS (ddr); - dir_vects = DDR_DIR_VECTS (ddr); +struct rdg_vertex_info GTY(()) +{ + gimple stmt; + int index; +}; - /* Reset the information. */ - DDR_DIST_VECTS (ddr) = NULL; - DDR_DIR_VECTS (ddr) = NULL; +/* Returns the index of STMT in RDG. */ - /* Compute the same information using Omega. */ - if (!init_omega_for_ddr (ddr, &maybe_dependent)) - goto csys_dont_know; +int +rdg_vertex_for_stmt (struct graph *rdg, gimple stmt) +{ + struct rdg_vertex_info rvi, *slot; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Omega Analyzer\n"); - dump_data_dependence_relation (dump_file, ddr); - } + rvi.stmt = stmt; + slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi); - /* Check that we get the same information. */ - if (maybe_dependent) - gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects, - dir_vects)); - } - } - else - 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 - { - csys_dont_know:; - dependence_stats.num_dependence_undetermined++; + if (!slot) + return -1; - 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"); + return slot->index; } -/* This computes the dependence relation for the same data - reference into DDR. */ +/* Creates an edge in RDG for each distance vector from DDR. The + order that we keep track of in the RDG is the order in which + statements have to be executed. */ static void -compute_self_dependence (struct data_dependence_relation *ddr) +create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr) { - unsigned int i; - struct subscript *subscript; - - for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript); - i++) + struct graph_edge *e; + int va, vb; + data_reference_p dra = DDR_A (ddr); + data_reference_p drb = DDR_B (ddr); + unsigned level = ddr_dependence_level (ddr); + + /* For non scalar dependences, when the dependence is REVERSED, + statement B has to be executed before statement A. */ + if (level > 0 + && !DDR_REVERSED_P (ddr)) { - /* The accessed index overlaps for each iteration. */ - SUB_CONFLICTS_IN_A (subscript) - = conflict_fn (1, affine_fn_cst (integer_zero_node)); - SUB_CONFLICTS_IN_B (subscript) - = conflict_fn (1, affine_fn_cst (integer_zero_node)); - SUB_LAST_CONFLICT (subscript) = chrec_dont_know; + data_reference_p tmp = dra; + dra = drb; + drb = tmp; } - /* 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))); + va = rdg_vertex_for_stmt (rdg, DR_STMT (dra)); + vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb)); + + if (va < 0 || vb < 0) + return; + + e = add_edge (rdg, va, vb); + e->data = XNEW (struct rdg_edge); + + RDGE_LEVEL (e) = level; + RDGE_RELATION (e) = ddr; + + /* Determines the type of the data dependence. */ + if (DR_IS_READ (dra) && DR_IS_READ (drb)) + RDGE_TYPE (e) = input_dd; + else if (!DR_IS_READ (dra) && !DR_IS_READ (drb)) + RDGE_TYPE (e) = output_dd; + else if (!DR_IS_READ (dra) && DR_IS_READ (drb)) + RDGE_TYPE (e) = flow_dd; + else if (DR_IS_READ (dra) && !DR_IS_READ (drb)) + RDGE_TYPE (e) = anti_dd; } -/* 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. */ +/* Creates dependence edges in RDG for all the uses of DEF. IDEF is + the index of DEF in RDG. */ -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) +static void +create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef) { - struct data_dependence_relation *ddr; - struct data_reference *a, *b; - unsigned int i, j; + use_operand_p imm_use_p; + imm_use_iterator iterator; + + FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def) + { + struct graph_edge *e; + int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p)); - 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 (use < 0) + continue; - 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); - } + e = add_edge (rdg, idef, use); + e->data = XNEW (struct rdg_edge); + RDGE_TYPE (e) = flow_dd; + RDGE_RELATION (e) = NULL; + } } -/* Stores the locations of memory references in STMT to REFERENCES. Returns - true if STMT clobbers memory, false otherwise. */ +/* Creates the edges of the reduced dependence graph RDG. */ -bool -get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references) +static void +create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs) { - bool clobbers_memory = false; - data_ref_loc *ref; - tree *op0, *op1, call; + int i; + struct data_dependence_relation *ddr; + def_operand_p def_p; + ssa_op_iter iter; - *references = NULL; + for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + create_rdg_edge_for_ddr (rdg, ddr); - /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects. - Calls have side-effects, except those to const or pure - functions. */ - call = get_call_expr_in (stmt); - if ((call - && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE))) - || (TREE_CODE (stmt) == ASM_EXPR - && ASM_VOLATILE_P (stmt))) - clobbers_memory = true; + for (i = 0; i < rdg->n_vertices; i++) + FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i), + iter, SSA_OP_DEF) + create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i); +} - if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) - return clobbers_memory; +/* Build the vertices of the reduced dependence graph RDG. */ + +void +create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts) +{ + int i, j; + gimple stmt; - if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) + for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++) { - op0 = &GIMPLE_STMT_OPERAND (stmt, 0); - op1 = &GIMPLE_STMT_OPERAND (stmt, 1); - - if (DECL_P (*op1) - || REFERENCE_CLASS_P (*op1)) - { - ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); - ref->pos = op1; - ref->is_read = true; - } + VEC (data_ref_loc, heap) *references; + data_ref_loc *ref; + struct vertex *v = &(rdg->vertices[i]); + struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info); + struct rdg_vertex_info **slot; + + rvi->stmt = stmt; + rvi->index = i; + slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT); + + if (!*slot) + *slot = rvi; + else + free (rvi); - if (DECL_P (*op0) - || REFERENCE_CLASS_P (*op0)) - { - ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); - ref->pos = op0; - ref->is_read = false; - } + v->data = XNEW (struct rdg_vertex); + RDG_STMT (rdg, i) = stmt; + + RDG_MEM_WRITE_STMT (rdg, i) = false; + RDG_MEM_READS_STMT (rdg, i) = false; + if (gimple_code (stmt) == GIMPLE_PHI) + continue; + + get_references_in_stmt (stmt, &references); + for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++) + if (!ref->is_read) + RDG_MEM_WRITE_STMT (rdg, i) = true; + else + RDG_MEM_READS_STMT (rdg, i) = true; + + VEC_free (data_ref_loc, heap, references); } +} + +/* Initialize STMTS with all the statements of LOOP. When + INCLUDE_PHIS is true, include also the PHI nodes. The order in + which we discover statements is important as + generate_loops_for_partition is using the same traversal for + identifying statements. */ + +static void +stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) +{ + unsigned int i; + basic_block *bbs = get_loop_body_in_dom_order (loop); - if (call) + for (i = 0; i < loop->num_nodes; i++) { - unsigned i, n = call_expr_nargs (call); + basic_block bb = bbs[i]; + gimple_stmt_iterator bsi; + gimple stmt; - for (i = 0; i < n; i++) - { - op0 = &CALL_EXPR_ARG (call, i); + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi)); - if (DECL_P (*op0) - || REFERENCE_CLASS_P (*op0)) - { - ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); - ref->pos = op0; - ref->is_read = true; - } + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + stmt = gsi_stmt (bsi); + if (gimple_code (stmt) != GIMPLE_LABEL) + VEC_safe_push (gimple, heap, *stmts, stmt); } } - return clobbers_memory; + free (bbs); } -/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable - reference, returns false, otherwise returns true. */ +/* Returns true when all the dependences are computable. */ static bool -find_data_references_in_stmt (tree stmt, - VEC (data_reference_p, heap) **datarefs) +known_dependences_p (VEC (ddr_p, heap) *dependence_relations) { - unsigned i; - VEC (data_ref_loc, heap) *references; - data_ref_loc *ref; - bool ret = true; - data_reference_p dr; + ddr_p ddr; + unsigned int i; - if (get_references_in_stmt (stmt, &references)) - { - VEC_free (data_ref_loc, heap, references); + for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) + if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) return false; - } + + return true; +} - for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++) - { - dr = create_data_ref (*ref->pos, stmt, ref->is_read); - if (dr) - VEC_safe_push (data_reference_p, heap, *datarefs, dr); - else - { - ret = false; - break; - } - } - VEC_free (data_ref_loc, heap, references); - return ret; +/* Computes a hash function for element ELT. */ + +static hashval_t +hash_stmt_vertex_info (const void *elt) +{ + const struct rdg_vertex_info *const rvi = + (const struct rdg_vertex_info *) elt; + gimple stmt = rvi->stmt; + + return htab_hash_pointer (stmt); } -/* 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. */ +/* Compares database elements E1 and E2. */ -tree -find_data_references_in_loop (struct loop *loop, - VEC (data_reference_p, heap) **datarefs) +static int +eq_stmt_vertex_info (const void *e1, const void *e2) { - basic_block bb, *bbs; - unsigned int i; - block_stmt_iterator bsi; + const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1; + const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2; - bbs = get_loop_body (loop); + return elt1->stmt == elt2->stmt; +} - for (i = 0; i < loop->num_nodes; i++) - { - bb = bbs[i]; +/* Free the element E. */ - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - tree stmt = bsi_stmt (bsi); +static void +hash_stmt_vertex_del (void *e) +{ + free (e); +} - if (!find_data_references_in_stmt (stmt, datarefs)) - { - struct data_reference *res; - 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); +/* Build the Reduced Dependence Graph (RDG) with one vertex per + statement of the loop nest, and one edge per data dependence or + scalar dependence. */ - free (bbs); - return chrec_dont_know; - } - } - } - free (bbs); +struct graph * +build_empty_rdg (int n_stmts) +{ + int nb_data_refs = 10; + struct graph *rdg = new_graph (n_stmts); - return NULL_TREE; + rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info, + eq_stmt_vertex_info, hash_stmt_vertex_del); + return rdg; } -/* Recursive helper function. */ +/* Build the Reduced Dependence Graph (RDG) with one vertex per + statement of the loop nest, and one edge per data dependence or + scalar dependence. */ -static bool -find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest) +struct graph * +build_rdg (struct loop *loop) { - /* Inner loops of the nest should not contain siblings. Example: - when there are two consecutive loops, + int nb_data_refs = 10; + struct graph *rdg = NULL; + VEC (ddr_p, heap) *dependence_relations; + VEC (data_reference_p, heap) *datarefs; + VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs); + + dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ; + datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs); + compute_data_dependences_for_loop (loop, + false, + &datarefs, + &dependence_relations); + + if (!known_dependences_p (dependence_relations)) + { + free_dependence_relations (dependence_relations); + free_data_refs (datarefs); + VEC_free (gimple, heap, stmts); - | loop_0 - | loop_1 - | A[{0, +, 1}_1] - | endloop_1 - | loop_2 - | A[{0, +, 1}_2] - | endloop_2 - | endloop_0 + return rdg; + } - the dependence relation cannot be captured by the distance - abstraction. */ - if (loop->next) - return false; + stmts_from_loop (loop, &stmts); + rdg = build_empty_rdg (VEC_length (gimple, stmts)); - VEC_safe_push (loop_p, heap, *loop_nest, loop); - if (loop->inner) - return find_loop_nest_1 (loop->inner, loop_nest); - return true; + rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info, + eq_stmt_vertex_info, hash_stmt_vertex_del); + create_rdg_vertices (rdg, stmts); + create_rdg_edges (rdg, dependence_relations); + + VEC_free (gimple, heap, stmts); + return rdg; } -/* 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. */ +/* Free the reduced dependence graph RDG. */ -static bool -find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest) +void +free_rdg (struct graph *rdg) { - VEC_safe_push (loop_p, heap, *loop_nest, loop); - if (loop->inner) - return find_loop_nest_1 (loop->inner, loop_nest); - return true; + int i; + + for (i = 0; i < rdg->n_vertices; i++) + free (rdg->vertices[i].data); + + htab_delete (rdg->indices); + free_graph (rdg); } -/* 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. */ +/* Initialize STMTS with all the statements of LOOP that contain a + store to memory. */ 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) +stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) { - struct loop *loop_nest = loop; - VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3); - - memset (&dependence_stats, 0, sizeof (dependence_stats)); + unsigned int i; + basic_block *bbs = get_loop_body_in_dom_order (loop); - /* 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) + for (i = 0; i < loop->num_nodes; i++) { - struct data_dependence_relation *ddr; + basic_block bb = bbs[i]; + gimple_stmt_iterator bsi; - /* 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); + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi), SSA_OP_VDEF)) + VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi)); } - 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"); + free (bbs); +} - 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); +/* For a data reference REF, return the declaration of its base + address or NULL_TREE if the base is not determined. */ - 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); +static inline tree +ref_base_address (gimple stmt, data_ref_loc *ref) +{ + tree base = NULL_TREE; + tree base_address; + struct data_reference *dr = XCNEW (struct data_reference); - 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); + DR_STMT (dr) = stmt; + DR_REF (dr) = *ref->pos; + dr_analyze_innermost (dr); + base_address = DR_BASE_ADDRESS (dr); - 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); + if (!base_address) + goto end; - 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); - } + switch (TREE_CODE (base_address)) + { + case ADDR_EXPR: + base = TREE_OPERAND (base_address, 0); + break; + + default: + base = base_address; + break; + } + + end: + free_data_ref (dr); + return base; } -/* Entry point (for testing only). Analyze all the data references - and the dependence relations in LOOP. +/* Determines whether the statement from vertex V of the RDG has a + definition used outside the loop that contains this statement. */ - 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. */ -static void -analyze_all_data_dependences (struct loop *loop) +bool +rdg_defs_used_in_other_loops_p (struct graph *rdg, int v) { - 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); + gimple stmt = RDG_STMT (rdg, v); + struct loop *loop = loop_containing_stmt (stmt); + use_operand_p imm_use_p; + imm_use_iterator iterator; + ssa_op_iter it; + def_operand_p def_p; - /* Compute DDs on the whole function. */ - compute_data_dependences_for_loop (loop, false, &datarefs, - &dependence_relations); + if (!loop) + return true; - if (dump_file) + FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF) { - dump_data_dependence_relations (dump_file, dependence_relations); - fprintf (dump_file, "\n\n"); + FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p)) + { + if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop) + return true; + } + } - if (dump_flags & TDF_DETAILS) - dump_dist_dir_vectors (dump_file, dependence_relations); + return false; +} - 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; +/* Determines whether statements S1 and S2 access to similar memory + locations. Two memory accesses are considered similar when they + have the same base address declaration, i.e. when their + ref_base_address is the same. */ - for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) +bool +have_similar_memory_accesses (gimple s1, gimple s2) +{ + bool res = false; + unsigned i, j; + VEC (data_ref_loc, heap) *refs1, *refs2; + data_ref_loc *ref1, *ref2; + + get_references_in_stmt (s1, &refs1); + get_references_in_stmt (s2, &refs2); + + for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++) + { + tree base1 = ref_base_address (s1, ref1); + + if (base1) + for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++) + if (base1 == ref_base_address (s2, ref2)) { - 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++; + res = true; + goto end; } - - gather_stats_on_scev_database (); - } } - free_dependence_relations (dependence_relations); - free_data_refs (datarefs); + end: + VEC_free (data_ref_loc, heap, refs1); + VEC_free (data_ref_loc, heap, refs2); + return res; } -/* Computes all the data dependences and check that the results of - several analyzers are the same. */ +/* Helper function for the hashtab. */ -void -tree_check_data_deps (void) +static int +have_similar_memory_accesses_1 (const void *s1, const void *s2) { - loop_iterator li; - struct loop *loop_nest; - - FOR_EACH_LOOP (li, loop_nest, 0) - analyze_all_data_dependences (loop_nest); + return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1), + CONST_CAST_GIMPLE ((const_gimple) s2)); } -/* Free the memory used by a data dependence relation DDR. */ +/* Helper function for the hashtab. */ -void -free_dependence_relation (struct data_dependence_relation *ddr) +static hashval_t +ref_base_address_1 (const void *s) { - if (ddr == NULL) - return; + gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s); + unsigned i; + VEC (data_ref_loc, heap) *refs; + data_ref_loc *ref; + hashval_t res = 0; - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) - free_subscripts (DDR_SUBSCRIPTS (ddr)); + get_references_in_stmt (stmt, &refs); - free (ddr); + for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++) + if (!ref->is_read) + { + res = htab_hash_pointer (ref_base_address (stmt, ref)); + break; + } + + VEC_free (data_ref_loc, heap, refs); + return res; } -/* Free the memory used by the data dependence relations from - DEPENDENCE_RELATIONS. */ +/* Try to remove duplicated write data references from STMTS. */ -void -free_dependence_relations (VEC (ddr_p, heap) *dependence_relations) +void +remove_similar_memory_refs (VEC (gimple, heap) **stmts) { - unsigned int i; - struct data_dependence_relation *ddr; - VEC (loop_p, heap) *loop_nest = NULL; + unsigned i; + gimple stmt; + htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1, + have_similar_memory_accesses_1, NULL); - for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) + for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); ) { - if (ddr == NULL) - continue; - if (loop_nest == NULL) - loop_nest = DDR_LOOP_NEST (ddr); + void **slot; + + slot = htab_find_slot (seen, stmt, INSERT); + + if (*slot) + VEC_ordered_remove (gimple, *stmts, i); else - gcc_assert (DDR_LOOP_NEST (ddr) == NULL - || DDR_LOOP_NEST (ddr) == loop_nest); - free_dependence_relation (ddr); + { + *slot = (void *) stmt; + i++; + } } - if (loop_nest) - VEC_free (loop_p, heap, loop_nest); - VEC_free (ddr_p, heap, dependence_relations); + htab_delete (seen); } -/* Free the memory used by the data references from DATAREFS. */ +/* Returns the index of PARAMETER in the parameters vector of the + ACCESS_MATRIX. If PARAMETER does not exist return -1. */ -void -free_data_refs (VEC (data_reference_p, heap) *datarefs) +int +access_matrix_get_index_for_parameter (tree parameter, + struct access_matrix *access_matrix) { - unsigned int i; - struct data_reference *dr; + int i; + VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix); + tree lambda_parameter; - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) - free_data_ref (dr); - VEC_free (data_reference_p, heap, datarefs); -} + for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++) + if (lambda_parameter == parameter) + return i + AM_NB_INDUCTION_VARS (access_matrix); + return -1; +}