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
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
+<http://www.gnu.org/licenses/>. */
/* This pass walks a given loop structure searching for array
references. The information about the array accesses is recorded
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);
fprintf (file, "\n\n");
}
-\f
-
-/* 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". */
+/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
+ will be ssizetype. */
-static tree
-analyze_array_indexes (struct loop *loop,
- VEC(tree,heap) **access_fns,
- tree ref, tree stmt)
+void
+split_constant_offset (tree exp, tree *var, tree *off)
{
- tree opnd0, opnd1;
- tree access_fn;
+ tree type = TREE_TYPE (exp), otype;
+ tree var0, var1;
+ tree off0, off1;
+ enum tree_code code;
- opnd0 = TREE_OPERAND (ref, 0);
- opnd1 = TREE_OPERAND (ref, 1);
+ *var = exp;
+ STRIP_NOPS (exp);
+ otype = TREE_TYPE (exp);
+ code = TREE_CODE (exp);
- /* 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, exp);
+ return;
- 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:
+ code = PLUS_EXPR;
+ /* FALLTHROUGH */
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
+ split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1);
+ *var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype,
+ var0, var1));
+ *off = size_binop (code, off0, off1);
+ return;
- /* Return the base name of the data access. */
- else
- return opnd0;
-}
+ case MULT_EXPR:
+ off1 = TREE_OPERAND (exp, 1);
+ if (TREE_CODE (off1) != INTEGER_CST)
+ break;
+
+ split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
+ *var = fold_convert (type, fold_build2 (MULT_EXPR, otype,
+ var0, off1));
+ *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, off1));
+ return;
-/* 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. */
+ case ADDR_EXPR:
+ {
+ tree op, base, poffset;
+ HOST_WIDE_INT pbitsize, pbitpos;
+ enum machine_mode pmode;
+ int punsignedp, pvolatilep;
-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);;
+ op = TREE_OPERAND (exp, 0);
+ if (!handled_component_p (op))
+ break;
- 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");
- }
+ base = get_inner_reference (op, &pbitsize, &pbitpos, &poffset,
+ &pmode, &punsignedp, &pvolatilep, 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;
+ if (pbitpos % BITS_PER_UNIT != 0)
+ break;
+ base = build_fold_addr_expr (base);
+ off0 = ssize_int (pbitpos / BITS_PER_UNIT);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
+ 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));
+ }
- return res;
+ 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 (TREE_CODE (var0) == NOP_EXPR
+ || TREE_CODE (var0) == CONVERT_EXPR)
+ {
+ 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)
+ break;
+
+ *var = var0;
+ *off = off0;
+ return;
+ }
+
+ case SSA_NAME:
+ {
+ tree def_stmt = SSA_NAME_DEF_STMT (exp);
+ if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT)
+ {
+ tree def_stmt_rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
+
+ if (!TREE_SIDE_EFFECTS (def_stmt_rhs)
+ && EXPR_P (def_stmt_rhs)
+ && !REFERENCE_CLASS_P (def_stmt_rhs)
+ && !get_call_expr_in (def_stmt_rhs))
+ {
+ split_constant_offset (def_stmt_rhs, &var0, &off0);
+ var0 = fold_convert (type, var0);
+ *var = var0;
+ *off = off0;
+ return;
+ }
+ }
+ break;
+ }
+
+ default:
+ break;
+ }
+
+ *off = ssize_int (0);
}
-/* For a data reference REF contained in the statement STMT, initialize
- a DATA_REFERENCE structure, and return it. */
+/* Returns the address ADDR of an object in a canonical shape (without nop
+ casts, and with type of pointer to the object). */
-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)
+static tree
+canonicalize_base_object_address (tree addr)
{
- struct data_reference *res = XNEW (struct data_reference);
- VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
+ tree orig = addr;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(init_pointer_ref \n");
- fprintf (dump_file, " (ref = ");
- print_generic_stmt (dump_file, ref, 0);
- fprintf (dump_file, ")\n");
- }
+ STRIP_NOPS (addr);
- 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;
+ /* 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 (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
+ if (TREE_CODE (addr) != ADDR_EXPR)
+ return addr;
- return res;
+ 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. */
-static struct data_reference *
-analyze_indirect_ref (tree stmt, tree ref, bool is_read)
+void
+dr_analyze_innermost (struct data_reference *dr)
{
+ tree 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: ");
- STRIP_NOPS (init);
- if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nBad access function of ptr: ");
- print_generic_expr (dump_file, ref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL;
- }
+ base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
+ &pmode, &punsignedp, &pvolatilep, false);
+ gcc_assert (base != NULL_TREE);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (pbitpos % BITS_PER_UNIT != 0)
{
- 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: bit offset alignment.\n");
+ return;
}
- if (!expr_invariant_in_loop_p (loop, init))
+ base = build_fold_addr_expr (base);
+ if (!simple_iv (loop, stmt, base, &base_iv, false))
{
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
+ fprintf (dump_file, "failed: evolution of base is not affine.\n");
+ return;
}
- else
+ if (!poffset)
{
- 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");
+ offset_iv.base = ssize_int (0);
+ offset_iv.step = ssize_int (0);
}
- 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. */
-
-static tree
-strip_conversion (tree expr)
-{
- tree to, ti, oprnd0;
-
- while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
+ else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
{
- 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;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "failed: evolution of offset is not affine.\n");
+ return;
}
- return expr;
-}
-\f
-/* Function analyze_offset_expr
+ 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);
- 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.
+ step = size_binop (PLUS_EXPR,
+ fold_convert (ssizetype, base_iv.step),
+ fold_convert (ssizetype, offset_iv.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_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
- STEP is an evolution of the data reference in this loop in bytes.
- In the above example, STEP is C_j.
+ DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
+ DR_INIT (dr) = init;
+ DR_STEP (dr) = step;
- 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.
+ DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
-*/
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "success.\n");
+}
-static bool
-analyze_offset_expr (tree expr,
- struct loop *loop,
- tree *initial_offset,
- tree *misalign,
- tree *aligned_to,
- tree *step)
-{
- tree oprnd0;
- tree oprnd1;
- tree left_offset = ssize_int (0);
- tree right_offset = ssize_int (0);
- tree left_misalign = ssize_int (0);
- tree right_misalign = ssize_int (0);
- tree left_step = ssize_int (0);
- tree right_step = ssize_int (0);
- enum tree_code code;
- tree init, evolution;
- tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
-
- *step = NULL_TREE;
- *misalign = NULL_TREE;
- *aligned_to = NULL_TREE;
- *initial_offset = NULL_TREE;
-
- /* Strip conversions that don't narrow the mode. */
- expr = strip_conversion (expr);
- if (!expr)
- return false;
-
- /* Stop conditions:
- 1. Constant. */
- if (TREE_CODE (expr) == INTEGER_CST)
- {
- *initial_offset = fold_convert (ssizetype, expr);
- *misalign = fold_convert (ssizetype, expr);
- *step = ssize_int (0);
- return true;
- }
-
- /* 2. Variable. Try to substitute with initial_condition of the corresponding
- access_fn in the current loop. */
- if (SSA_VAR_P (expr))
- {
- tree access_fn = analyze_scalar_evolution (loop, expr);
-
- if (access_fn == chrec_dont_know)
- /* No access_fn. */
- return false;
-
- init = initial_condition_in_loop_num (access_fn, loop->num);
- if (!expr_invariant_in_loop_p (loop, init))
- /* Not enough information: may be not loop invariant.
- E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
- initial_condition is D, but it depends on i - loop's induction
- variable. */
- return false;
-
- evolution = evolution_part_in_loop_num (access_fn, loop->num);
- if (evolution && TREE_CODE (evolution) != INTEGER_CST)
- /* Evolution is not constant. */
- return false;
-
- if (TREE_CODE (init) == INTEGER_CST)
- *misalign = fold_convert (ssizetype, init);
- else
- /* Not constant, misalignment cannot be calculated. */
- *misalign = NULL_TREE;
-
- *initial_offset = fold_convert (ssizetype, init);
-
- *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
- return true;
- }
-
- /* Recursive computation. */
- if (!BINARY_CLASS_P (expr))
- {
- /* We expect to get binary expressions (PLUS/MINUS and MULT). */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nNot binary expression ");
- print_generic_expr (dump_file, expr, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return false;
- }
- oprnd0 = TREE_OPERAND (expr, 0);
- oprnd1 = TREE_OPERAND (expr, 1);
-
- if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
- &left_aligned_to, &left_step)
- || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
- &right_aligned_to, &right_step))
- return false;
-
- /* The type of the operation: plus, minus or mult. */
- code = TREE_CODE (expr);
- switch (code)
- {
- case MULT_EXPR:
- if (TREE_CODE (right_offset) != INTEGER_CST)
- /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
- sized types.
- FORNOW: We don't support such cases. */
- return false;
-
- /* Strip conversions that don't narrow the mode. */
- left_offset = strip_conversion (left_offset);
- if (!left_offset)
- return false;
- /* Misalignment computation. */
- if (SSA_VAR_P (left_offset))
- {
- /* If the left side contains variables that can't be substituted with
- constants, the misalignment is unknown. However, if the right side
- is a multiple of some alignment, we know that the expression is
- aligned to it. Therefore, we record such maximum possible value.
- */
- *misalign = NULL_TREE;
- *aligned_to = ssize_int (highest_pow2_factor (right_offset));
- }
- else
- {
- /* The left operand was successfully substituted with constant. */
- if (left_misalign)
- {
- /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
- NULL_TREE. */
- *misalign = size_binop (code, left_misalign, right_misalign);
- if (left_aligned_to && right_aligned_to)
- *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
- right_aligned_to);
- else
- *aligned_to = left_aligned_to ?
- left_aligned_to : right_aligned_to;
- }
- else
- *misalign = NULL_TREE;
- }
-
- /* Step calculation. */
- /* Multiply the step by the right operand. */
- *step = size_binop (MULT_EXPR, left_step, right_offset);
- break;
-
- case PLUS_EXPR:
- case MINUS_EXPR:
- /* Combine the recursive calculations for step and misalignment. */
- *step = size_binop (code, left_step, right_step);
-
- /* Unknown alignment. */
- if ((!left_misalign && !left_aligned_to)
- || (!right_misalign && !right_aligned_to))
- {
- *misalign = NULL_TREE;
- *aligned_to = NULL_TREE;
- break;
- }
-
- if (left_misalign && right_misalign)
- *misalign = size_binop (code, left_misalign, right_misalign);
- else
- *misalign = left_misalign ? left_misalign : right_misalign;
-
- if (left_aligned_to && right_aligned_to)
- *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
- else
- *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
-
- break;
-
- default:
- gcc_unreachable ();
- }
-
- /* Compute offset. */
- *initial_offset = fold_convert (ssizetype,
- fold_build2 (code, TREE_TYPE (left_offset),
- left_offset,
- right_offset));
- return true;
-}
-
-/* Function address_analysis
-
- Return the BASE of the address expression EXPR.
- Also compute the OFFSET from BASE, MISALIGN and STEP.
-
- Input:
- EXPR - the address expression that is being analyzed
- STMT - the statement that contains EXPR or its original memory reference
- IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
- DR - data_reference struct for the original memory reference
-
- Output:
- BASE (returned value) - the base of the data reference EXPR.
- INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
- MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
- computation is impossible
- ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
- calculated (doesn't depend on variables)
- STEP - evolution of EXPR in the loop
-
- If something unexpected is encountered (an unsupported form of data-ref),
- then NULL_TREE is returned.
- */
-
-static tree
-address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
- tree *offset, tree *misalign, tree *aligned_to, tree *step)
-{
- tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
- tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
- tree dummy, address_aligned_to = NULL_TREE;
- struct ptr_info_def *dummy1;
- subvar_t dummy2;
-
- switch (TREE_CODE (expr))
- {
- case PLUS_EXPR:
- case MINUS_EXPR:
- /* EXPR is of form {base +/- offset} (or {offset +/- base}). */
- oprnd0 = TREE_OPERAND (expr, 0);
- oprnd1 = TREE_OPERAND (expr, 1);
-
- STRIP_NOPS (oprnd0);
- STRIP_NOPS (oprnd1);
-
- /* Recursively try to find the base of the address contained in EXPR.
- For offset, the returned base will be NULL. */
- base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
- &address_misalign, &address_aligned_to,
- step);
-
- base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset,
- &address_misalign, &address_aligned_to,
- step);
-
- /* We support cases where only one of the operands contains an
- address. */
- if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file,
- "\neither more than one address or no addresses in expr ");
- print_generic_expr (dump_file, expr, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
+/* Determines the base object and the list of indices of memory reference
+ DR, analyzed in loop nest NEST. */
- /* To revert STRIP_NOPS. */
- oprnd0 = TREE_OPERAND (expr, 0);
- oprnd1 = TREE_OPERAND (expr, 1);
-
- offset_expr = base_addr0 ?
- fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
-
- /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
- a number, we can add it to the misalignment value calculated for base,
- otherwise, misalignment is NULL. */
- if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
- {
- *misalign = size_binop (TREE_CODE (expr), address_misalign,
- offset_expr);
- *aligned_to = address_aligned_to;
- }
- else
- {
- *misalign = NULL_TREE;
- *aligned_to = NULL_TREE;
- }
-
- /* Combine offset (from EXPR {base + offset}) with the offset calculated
- for base. */
- *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
- return base_addr0 ? base_addr0 : base_addr1;
-
- case ADDR_EXPR:
- base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
- &dr, offset, misalign, aligned_to, step,
- &dummy, &dummy1, &dummy2);
- return base_address;
-
- case SSA_NAME:
- if (!POINTER_TYPE_P (TREE_TYPE (expr)))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nnot pointer SSA_NAME ");
- print_generic_expr (dump_file, expr, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
- *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
- *misalign = ssize_int (0);
- *offset = ssize_int (0);
- *step = ssize_int (0);
- return expr;
-
- default:
- return NULL_TREE;
- }
-}
-
-
-/* Function object_analysis
-
- Create a data-reference structure DR for MEMREF.
- Return the BASE of the data reference MEMREF if the analysis is possible.
- Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
- E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
- 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
- instantiated with initial_conditions of access_functions of variables,
- and STEP is the evolution of the DR_REF in this loop.
-
- Function get_inner_reference is used for the above in case of ARRAY_REF and
- COMPONENT_REF.
-
- The structure of the function is as follows:
- Part 1:
- Case 1. For handled_component_p refs
- 1.1 build data-reference structure for MEMREF
- 1.2 call get_inner_reference
- 1.2.1 analyze offset expr received from get_inner_reference
- (fall through with BASE)
- Case 2. For declarations
- 2.1 set MEMTAG
- Case 3. For INDIRECT_REFs
- 3.1 build data-reference structure for MEMREF
- 3.2 analyze evolution and initial condition of MEMREF
- 3.3 set data-reference structure for MEMREF
- 3.4 call address_analysis to analyze INIT of the access function
- 3.5 extract memory tag
-
- Part 2:
- Combine the results of object and address analysis to calculate
- INITIAL_OFFSET, STEP and misalignment info.
-
- Input:
- MEMREF - the memory reference that is being analyzed
- STMT - the statement that contains MEMREF
- IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
-
- Output:
- BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
- E.g, if MEMREF is a.b[k].c[i][j] the returned
- base is &a.
- DR - data_reference struct for MEMREF
- INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
- MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
- ALIGNMENT or NULL_TREE if the computation is impossible
- ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
- calculated (doesn't depend on variables)
- STEP - evolution of the DR_REF in the loop
- MEMTAG - memory tag for aliasing purposes
- PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
- SUBVARS - Sub-variables of the variable
-
- If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
- but DR can be created anyway.
-
-*/
-
-static tree
-object_analysis (tree memref, tree stmt, bool is_read,
- struct data_reference **dr, tree *offset, tree *misalign,
- tree *aligned_to, tree *step, tree *memtag,
- struct ptr_info_def **ptr_info, subvar_t *subvars)
+static void
+dr_analyze_indices (struct data_reference *dr, struct loop *nest)
{
- 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;
+ tree stmt = DR_STMT (dr);
struct loop *loop = loop_containing_stmt (stmt);
- struct data_reference *ptr_dr = NULL;
- tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
- tree comp_ref = NULL_TREE;
-
- *ptr_info = NULL;
+ VEC (tree, heap) *access_fns = NULL;
+ tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
+ tree base, off, access_fn;
- /* Part 1: */
- /* Case 1. handled_component_p refs. */
- if (handled_component_p (memref))
+ while (handled_component_p (aref))
{
- /* 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;
- }
- }
-
- /* 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 (TREE_CODE (aref) == ARRAY_REF)
{
- 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;
- }
+ op = TREE_OPERAND (aref, 1);
+ access_fn = analyze_scalar_evolution (loop, op);
+ access_fn = resolve_mixers (nest, access_fn);
+ VEC_safe_push (tree, heap, access_fns, access_fn);
- /* 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;
+ TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
}
-
- /* Add bit position to OFFSET and MISALIGN. */
-
- bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
- /* Check that there is no remainder in bits. */
- if (pbitpos%BITS_PER_UNIT)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nbit offset alignment.\n");
- return NULL_TREE;
- }
- object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
- if (object_misalign)
- object_misalign = size_binop (PLUS_EXPR, object_misalign,
- bit_pos_in_bytes);
- memref = base; /* To continue analysis of BASE. */
- /* fall through */
- }
-
- /* Part 1: Case 2. Declarations. */
- if (DECL_P (memref))
- {
- /* We expect to get a decl only if we already have a DR, or with
- COMPONENT_REFs of type 'a[i].b'. */
- if (!(*dr))
- {
- if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
- {
- *dr = 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;
+ aref = TREE_OPERAND (aref, 0);
}
- /* Part 1: Case 3. INDIRECT_REFs. */
- else if (TREE_CODE (memref) == INDIRECT_REF)
+ if (INDIRECT_REF_P (aref))
{
- tree ptr_ref = TREE_OPERAND (memref, 0);
- if (TREE_CODE (ptr_ref) == SSA_NAME)
- *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
-
- /* 3.1 build data-reference structure for MEMREF. */
- ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
- if (!ptr_dr)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "\nfailed to create dr for ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
- }
- return NULL_TREE;
- }
+ op = TREE_OPERAND (aref, 0);
+ access_fn = analyze_scalar_evolution (loop, op);
+ access_fn = resolve_mixers (nest, 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);
+ }
- /* 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;
- }
+ DR_BASE_OBJECT (dr) = ref;
+ DR_ACCESS_FNS (dr) = access_fns;
+}
- 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;
- }
+/* Extracts the alias analysis information from the memory reference DR. */
- /* 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)
+static void
+dr_analyze_alias (struct data_reference *dr)
+{
+ tree 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))
{
- /* MEMREF cannot be analyzed. */
- if (dump_file && (dump_flags & TDF_DETAILS))
+ addr = TREE_OPERAND (base, 0);
+ if (TREE_CODE (addr) == SSA_NAME)
{
- fprintf (dump_file, "\ndata-ref of unsupported type ");
- print_generic_expr (dump_file, memref, TDF_SLIM);
- fprintf (dump_file, "\n");
+ smt = symbol_mem_tag (SSA_NAME_VAR (addr));
+ DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
}
- return NULL_TREE;
}
- if (comp_ref)
- DR_REF (*dr) = comp_ref;
+ DR_SYMBOL_TAG (dr) = smt;
+ if (smt && var_can_have_subvars (smt))
+ DR_SUBVARS (dr) = get_subvars_for_var (smt);
- 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
+ vops = BITMAP_ALLOC (NULL);
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
{
- 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;
+ bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
}
- *step = size_binop (PLUS_EXPR, object_step, address_step);
- return base_address;
+ DR_VOPS (dr) = vops;
}
-/* Function analyze_offset.
-
- Extract INVARIANT and CONSTANT parts from OFFSET.
+/* Returns true if the address of DR is invariant. */
-*/
-static bool
-analyze_offset (tree offset, tree *invariant, tree *constant)
+static bool
+dr_address_invariant_p (struct data_reference *dr)
{
- 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;
+ unsigned i;
+ tree idx;
- /* 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);
+ for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++)
+ if (tree_contains_chrecs (idx, NULL))
+ return false;
- 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. */
+/* Frees data reference DR. */
static void
free_data_ref (data_reference_p dr)
{
- DR_FREE_ACCESS_FNS (dr);
+ BITMAP_FREE (DR_VOPS (dr));
+ VEC_free (tree, heap, DR_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
+/* 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. */
- 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 *
+create_data_ref (struct loop *nest, 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);
+ struct data_reference *dr;
- /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
- of DR. */
- if (constant)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- DR_INIT (dr) = fold_convert (ssizetype, constant);
- init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
- constant, type_size);
+ fprintf (dump_file, "Creating dr for ");
+ print_generic_expr (dump_file, memref, TDF_SLIM);
+ fprintf (dump_file, "\n");
}
- 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;
+ dr = XCNEW (struct data_reference);
+ DR_STMT (dr) = stmt;
+ DR_REF (dr) = memref;
+ DR_IS_READ (dr) = is_read;
- /* 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);
- }
+ dr_analyze_innermost (dr);
+ dr_analyze_indices (dr, nest);
+ dr_analyze_alias (dr);
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: ");
+ 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\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\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");
- 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;
}
{
unsigned i, n = VEC_length (tree, fna);
- gcc_assert (n == VEC_length (tree, fnb));
+ if (n != VEC_length (tree, fnb))
+ return false;
for (i = 0; i < n; i++)
if (!operand_equal_p (VEC_index (tree, fna, i),
return true;
}
+/* Returns true if FN is the zero constant function. */
+
+static bool
+affine_function_zero_p (affine_fn fn)
+{
+ return (integer_zerop (affine_function_base (fn))
+ && affine_function_constant_p (fn));
+}
+
+/* Returns a signed integer type with the largest precision from TA
+ and TB. */
+
+static tree
+signed_type_for_types (tree ta, tree tb)
+{
+ if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
+ return signed_type_for (ta);
+ else
+ return signed_type_for (tb);
+}
+
/* Applies operation OP on affine functions FNA and FNB, and returns the
result. */
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)));
+ {
+ tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
+ TREE_TYPE (VEC_index (tree, fnb, i)));
+
+ VEC_quick_push (tree, ret,
+ fold_build2 (op, type,
+ 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;
return fn;
}
+/* Returns true if the address of OBJ is invariant in LOOP. */
+
+static bool
+object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
+{
+ while (handled_component_p (obj))
+ {
+ if (TREE_CODE (obj) == ARRAY_REF)
+ {
+ /* 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 (!INDIRECT_REF_P (obj))
+ return true;
+
+ 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;
+ }
+
+ 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. */
+
+static 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;
+}
+
/* 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. */
VEC (loop_p, heap) *loop_nest)
{
struct data_dependence_relation *res;
- bool differ_p, known_dependence;
unsigned int i;
res = XNEW (struct data_dependence_relation);
DDR_A (res) = a;
DDR_B (res) = b;
DDR_LOOP_NEST (res) = NULL;
+ DDR_REVERSED_P (res) = false;
+ DDR_SUBSCRIPTS (res) = NULL;
+ DDR_DIR_VECTS (res) = NULL;
+ DDR_DIST_VECTS (res) = NULL;
if (a == NULL || b == NULL)
{
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))
+ /* If the data references do not alias, then they are independent. */
+ if (!dr_may_alias_p (a, b))
{
- DDR_ARE_DEPENDENT (res) = chrec_known;
+ DDR_ARE_DEPENDENT (res) = chrec_known;
return res;
}
- if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
- known_dependence = base_addr_differ_p (a, b, &differ_p);
- else
- known_dependence = base_object_differ_p (a, b, &differ_p);
-
- if (!known_dependence)
+ /* 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))
{
- /* Can't determine whether the data-refs access the same memory
- region. */
DDR_ARE_DEPENDENT (res) = chrec_dont_know;
return res;
}
- if (differ_p)
+ /* 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_known;
+ 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;
for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
{
DDR_ARE_DEPENDENT (ddr) = chrec;
free_subscripts (DDR_SUBSCRIPTS (ddr));
+ DDR_SUBSCRIPTS (ddr) = NULL;
}
/* The dependence relation DDR cannot be represented by a distance
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));
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))
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_TREE);
+ chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
+ difference = chrec_fold_minus (type, chrec_a, chrec_b);
switch (TREE_CODE (difference))
{
large as the number of iterations. If we have no reliable estimate,
the function returns false, otherwise returns true. */
-static bool
+bool
estimated_loop_iterations (struct loop *loop, bool conservative,
double_int *nit)
{
- tree numiter = number_of_exit_cond_executions (loop);
-
- /* If we have an exact value, use it. */
- if (TREE_CODE (numiter) == INTEGER_CST)
+ estimate_numbers_of_iterations_loop (loop);
+ if (conservative)
{
- *nit = tree_to_double_int (numiter);
- return true;
- }
+ if (!loop->any_upper_bound)
+ return false;
- /* If we have a measured profile and we do not ask for a conservative bound,
- use it. */
- if (!conservative && loop->header->count != 0)
- {
- *nit = uhwi_to_double_int (expected_loop_iterations (loop) + 1);
- return true;
+ *nit = loop->nb_iterations_upper_bound;
}
-
- /* Finally, try using a reliable estimate on number of iterations according
- to the size of the accessed data, if available. */
- estimate_numbers_of_iterations_loop (loop);
- if (loop->estimate_state == EST_AVAILABLE)
+ else
{
- *nit = loop->estimated_nb_iterations;
- return true;
+ if (!loop->any_estimate)
+ return false;
+
+ *nit = loop->nb_iterations_estimate;
}
- return false;
+ return true;
}
/* Similar to estimated_loop_iterations, but returns the estimate only
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_TREE);
+ chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
+ difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
if (!chrec_is_positive (initial_condition (difference), &value0))
{
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;
/* 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)
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)
/* Helper recursive function for initializing the matrix A. Returns
the initial value of CHREC. */
-static int
+static HOST_WIDE_INT
initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
{
gcc_assert (chrec);
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,
*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
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)
{
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))
{
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));
| 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;
*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
*last_conflicts = chrec_dont_know;
}
}
-
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
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))
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)). */
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
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_TREE);
+ chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
+ difference = chrec_fold_minus (type, chrec_a, chrec_b);
if (eq_evolutions_p (chrec_a, chrec_b))
{
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
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:
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))
/* 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));
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 ();
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))
{
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
same access functions. */
static bool
-same_access_functions (struct data_dependence_relation *ddr)
+same_access_functions (const struct data_dependence_relation *ddr)
{
unsigned i;
return true;
}
+/* Return true when the DDR contains only constant access functions. */
+
+static bool
+constant_access_functions (const struct data_dependence_relation *ddr)
+{
+ unsigned i;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (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)
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;
}
/* 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);
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;
}
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))
{
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);
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:
{
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
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;
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))
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;
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))
}
/* 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;
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);
+ tree fun_b = chrec_convert (type, access_fun_b, NULL_TREE);
+ 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. */
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)
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);
return true;
}
-/* This computes the affine dependence relation between A and B.
- CHREC_KNOWN is used for representing the independence between two
- accesses, while CHREC_DONT_KNOW is used for representing the unknown
- relation.
+/* 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)
+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);
{
dependence_stats.num_dependence_tests++;
- if (access_functions_are_affine_or_constant_p (dra)
- && access_functions_are_affine_or_constant_p (drb))
+ 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);
+ subscript_dependence_tester (ddr, loop_nest);
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
}
else
- subscript_dependence_tester (ddr);
+ subscript_dependence_tester (ddr, loop_nest);
}
/* As a last case, if the dependence cannot be determined, or if
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));
+ = conflict_fn (1, affine_fn_cst (integer_zero_node));
SUB_CONFLICTS_IN_B (subscript)
- = conflict_fn (1, affine_fn_cst (integer_zero_node));
+ = conflict_fn (1, affine_fn_cst (integer_zero_node));
SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
}
COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
relations. */
-static void
+void
compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
VEC (ddr_p, heap) **dependence_relations,
VEC (loop_p, heap) *loop_nest,
{
ddr = initialize_data_dependence_relation (a, b, loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
- compute_affine_dependence (ddr);
+ compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
}
if (compute_self_and_rr)
{
bool clobbers_memory = false;
data_ref_loc *ref;
- tree *op0, *op1, arg, call;
- call_expr_arg_iterator iter;
+ tree *op0, *op1, call;
*references = NULL;
op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
if (DECL_P (*op1)
- || REFERENCE_CLASS_P (*op1))
+ || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1)))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
ref->pos = op1;
}
if (DECL_P (*op0)
- || REFERENCE_CLASS_P (*op0))
+ || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
ref->pos = op0;
if (call)
{
- FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
+ unsigned i, n = call_expr_nargs (call);
+
+ for (i = 0; i < n; i++)
{
- op0 = &arg;
+ op0 = &CALL_EXPR_ARG (call, i);
+
if (DECL_P (*op0)
- || REFERENCE_CLASS_P (*op0))
+ || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
{
ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
ref->pos = op0;
}
/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
- reference, returns false, otherwise returns true. */
+ reference, returns false, otherwise returns true. NEST is the outermost
+ loop of the loop nest in that the references should be analyzed. */
static bool
-find_data_references_in_stmt (tree stmt,
+find_data_references_in_stmt (struct loop *nest, tree stmt,
VEC (data_reference_p, heap) **datarefs)
{
unsigned i;
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
+ 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
+static tree
find_data_references_in_loop (struct loop *loop,
VEC (data_reference_p, heap) **datarefs)
{
unsigned int i;
block_stmt_iterator bsi;
- bbs = get_loop_body (loop);
+ bbs = get_loop_body_in_dom_order (loop);
for (i = 0; i < loop->num_nodes; i++)
{
{
tree stmt = bsi_stmt (bsi);
- if (!find_data_references_in_stmt (stmt, datarefs))
+ if (!find_data_references_in_stmt (loop, 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;
+ res = XCNEW (struct data_reference);
VEC_safe_push (data_reference_p, heap, *datarefs, res);
free (bbs);
contain the loops from the outermost to the innermost, as they will
appear in the classic distance vector. */
-static bool
+bool
find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
{
VEC_safe_push (loop_p, heap, *loop_nest, loop);
VEC (data_reference_p, heap) **datarefs,
VEC (ddr_p, heap) **dependence_relations)
{
- struct loop *loop_nest = loop;
VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
memset (&dependence_stats, 0, sizeof (dependence_stats));
/* If the loop nest is not well formed, or one of the data references
is not computable, give up without spending time to compute other
dependences. */
- if (!loop_nest
- || !find_loop_nest (loop_nest, &vloops)
+ if (!loop
+ || !find_loop_nest (loop, &vloops)
|| find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
{
struct data_dependence_relation *ddr;
{
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))
+
+ if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
nb_basename_differ++;
else
nb_bot_relations++;
if (ddr == NULL)
return;
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
+ 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);
}
VEC_free (data_reference_p, heap, datarefs);
}
+\f
+
+/* Returns the index of STMT in RDG. */
+
+static int
+find_vertex_for_stmt (const struct graph *rdg, const_tree stmt)
+{
+ int i;
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ if (RDGV_STMT (&(rdg->vertices[i])) == stmt)
+ return i;
+
+ gcc_unreachable ();
+ return 0;
+}
+
+/* Creates an edge in RDG for each distance vector from DDR. */
+
+static void
+create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
+{
+ int va, vb;
+ data_reference_p dra;
+ data_reference_p drb;
+ struct graph_edge *e;
+
+ if (DDR_REVERSED_P (ddr))
+ {
+ dra = DDR_B (ddr);
+ drb = DDR_A (ddr);
+ }
+ else
+ {
+ dra = DDR_A (ddr);
+ drb = DDR_B (ddr);
+ }
+
+ va = find_vertex_for_stmt (rdg, DR_STMT (dra));
+ vb = find_vertex_for_stmt (rdg, DR_STMT (drb));
+
+ e = add_edge (rdg, va, vb);
+ e->data = XNEW (struct rdg_edge);
+
+ /* 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;
+}
+
+/* Creates dependence edges in RDG for all the uses of DEF. IDEF is
+ the index of DEF in RDG. */
+
+static void
+create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
+{
+ use_operand_p imm_use_p;
+ imm_use_iterator iterator;
+
+ FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
+ {
+ int use = find_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
+ struct graph_edge *e = add_edge (rdg, idef, use);
+
+ e->data = XNEW (struct rdg_edge);
+ RDGE_TYPE (e) = flow_dd;
+ }
+}
+
+/* Creates the edges of the reduced dependence graph RDG. */
+
+static void
+create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
+{
+ int i;
+ struct data_dependence_relation *ddr;
+ def_operand_p def_p;
+ ssa_op_iter iter;
+
+ 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);
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ FOR_EACH_PHI_OR_STMT_DEF (def_p, RDGV_STMT (&(rdg->vertices[i])),
+ iter, SSA_OP_ALL_DEFS)
+ create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
+}
+
+/* Build the vertices of the reduced dependence graph RDG. */
+
+static void
+create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts)
+{
+ int i;
+ tree s;
+
+ for (i = 0; VEC_iterate (tree, stmts, i, s); i++)
+ {
+ struct vertex *v = &(rdg->vertices[i]);
+
+ v->data = XNEW (struct rdg_vertex);
+ RDGV_STMT (v) = s;
+ }
+}
+
+/* Initialize STMTS with all the statements and PHI nodes of LOOP. */
+
+static void
+stmts_from_loop (struct loop *loop, VEC (tree, heap) **stmts)
+{
+ unsigned int i;
+ basic_block *bbs = get_loop_body_in_dom_order (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ tree phi;
+ basic_block bb = bbs[i];
+ block_stmt_iterator bsi;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ VEC_safe_push (tree, heap, *stmts, phi);
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ VEC_safe_push (tree, heap, *stmts, bsi_stmt (bsi));
+ }
+
+ free (bbs);
+}
+
+/* Returns true when all the dependences are computable. */
+
+static bool
+known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
+{
+ ddr_p ddr;
+ unsigned int i;
+
+ for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ return false;
+
+ return true;
+}
+
+/* Build a Reduced Dependence Graph with one vertex per statement of the
+ loop nest and one edge per data dependence or scalar dependence. */
+
+struct graph *
+build_rdg (struct loop *loop)
+{
+ int nb_data_refs = 10;
+ struct graph *rdg = NULL;
+ VEC (ddr_p, heap) *dependence_relations;
+ VEC (data_reference_p, heap) *datarefs;
+ VEC (tree, heap) *stmts = VEC_alloc (tree, heap, 10);
+
+ 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))
+ goto end_rdg;
+
+ stmts_from_loop (loop, &stmts);
+ rdg = new_graph (VEC_length (tree, stmts));
+ create_rdg_vertices (rdg, stmts);
+ create_rdg_edges (rdg, dependence_relations);
+
+ end_rdg:
+ free_dependence_relations (dependence_relations);
+ free_data_refs (datarefs);
+ VEC_free (tree, heap, stmts);
+
+ return rdg;
+}