This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix PR82397
On Sat, 7 Oct 2017, Richard Sandiford wrote:
> Richard Biener <rguenther@suse.de> writes:
> > I am testing the following patch to fix the qsort intransitiveness
> > of dr_group_sort_cmp. The patch removes the overly powerful
> > operand_equal_p checks (handling commutativity )
> > because those do not mix well with the sorting constraints.
> >
> > I am also testing a followup to address the missed equalities by
> > canonicalization -- the interesting trees happen to be all built
> > by split_constant_offset where we can do some elaborate canonicalization
> > in linear complexity (as opposed to operand_equal_p's exponential
> > handling or trying to handle it in data_ref_compare_tree where it would
> > be done at least multiple times during qsort invocation).
> >
> > Bootstrapped on x86_64-unknown-linux-gnu, testing still in progress
> > (so is a quick SPEC 2k6 build where the issue showed up in multiple
> > places).
> >
> > Richard.
> >
> > 2017-10-06 Richard Biener <rguenther@suse.de>
> >
> > PR tree-optimization/82397
> > * tree-vect-data-refs.c (dr_group_sort_cmp): Do not use
> > operand_equal_p but rely on data_ref_compare_tree for detecting
> > equalities.
> > (vect_analyze_data_ref_accesses): Use data_ref_compare_tree
> > to match up with dr_group_sort_cmp.
> >
> > * gfortran.dg/pr82397.f: New testcase.
> >
> > Index: gcc/tree-vect-data-refs.c
> > ===================================================================
> > --- gcc/tree-vect-data-refs.c (revision 253475)
> > +++ gcc/tree-vect-data-refs.c (working copy)
> > @@ -2727,43 +2727,30 @@ dr_group_sort_cmp (const void *dra_, con
> > return loopa->num < loopb->num ? -1 : 1;
> >
> > /* Ordering of DRs according to base. */
> > - if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
> > - {
> > - cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra),
> > - DR_BASE_ADDRESS (drb));
> > - if (cmp != 0)
> > - return cmp;
> > - }
> > + cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra),
> > + DR_BASE_ADDRESS (drb));
> > + if (cmp != 0)
> > + return cmp;
> >
> > /* And according to DR_OFFSET. */
> > - if (!dr_equal_offsets_p (dra, drb))
> > - {
> > - cmp = data_ref_compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
> > - if (cmp != 0)
> > - return cmp;
> > - }
> > + cmp = data_ref_compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
> > + if (cmp != 0)
> > + return cmp;
> >
> > /* Put reads before writes. */
> > if (DR_IS_READ (dra) != DR_IS_READ (drb))
> > return DR_IS_READ (dra) ? -1 : 1;
> >
> > /* Then sort after access size. */
> > - if (!operand_equal_p (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
> > - TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))), 0))
> > - {
> > - cmp = data_ref_compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
> > - TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
> > - if (cmp != 0)
> > - return cmp;
> > - }
> > + cmp = data_ref_compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
> > + TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
> > + if (cmp != 0)
> > + return cmp;
> >
> > /* And after step. */
> > - if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
> > - {
> > - cmp = data_ref_compare_tree (DR_STEP (dra), DR_STEP (drb));
> > - if (cmp != 0)
> > - return cmp;
> > - }
> > + cmp = data_ref_compare_tree (DR_STEP (dra), DR_STEP (drb));
> > + if (cmp != 0)
> > + return cmp;
> >
> > /* Then sort after DR_INIT. In case of identical DRs sort after stmt UID. */
> > cmp = tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb));
> > @@ -2835,9 +2822,9 @@ vect_analyze_data_ref_accesses (vec_info
> > and they are both either store or load (not load and store,
> > not masked loads or stores). */
> > if (DR_IS_READ (dra) != DR_IS_READ (drb)
> > - || !operand_equal_p (DR_BASE_ADDRESS (dra),
> > - DR_BASE_ADDRESS (drb), 0)
> > - || !dr_equal_offsets_p (dra, drb)
> > + || data_ref_compare_tree (DR_BASE_ADDRESS (dra),
> > + DR_BASE_ADDRESS (drb)) != 0
> > + || data_ref_compare_tree (DR_OFFSET (dra), DR_OFFSET (drb)) != 0
> > || !gimple_assign_single_p (DR_STMT (dra))
> > || !gimple_assign_single_p (DR_STMT (drb)))
> > break;
> > @@ -2851,7 +2838,7 @@ vect_analyze_data_ref_accesses (vec_info
> > break;
> >
> > /* Check that the data-refs have the same step. */
> > - if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
> > + if (data_ref_compare_tree (DR_STEP (dra), DR_STEP (drb)) != 0)
> > break;
> >
> > /* Do not place the same access in the interleaving chain twice. */
>
> I don't think data_ref_compare_tree is strong enough to replace
> operand_equal_p when equality is needed for correctness.
> A lot of data_ref_compare_tree just uses hash values and can
> return 0 for things that aren't actually equal. (Although maybe
> that's the bug...)
Hmm, yeah. I think it's unfortunate (and given how we consume
the ordered dataref set a possible wrong-code issue).
So the only issue is with comparing constants (plus stripping
sign-conversions maybe). I think for those types where no
total order exists we could resort to memcmp on native encodings.
I don't expect we run into anything but INTEGER_CSTs here.
After all the default case w/o checking expects tcc_expression
if not tcc_declaration unless TREE_OPERAND_LENGTH returns zero
in which case we just declare equality...
So I'm going to give the following some broader testing.
Richard.
2017-10-09 Richard Biener <rguenther@suse.de>
PR tree-optimization/82397
* tree-data-ref.c (data_ref_compare_tree): Make sure to return
equality only for semantically equal trees.
Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c (revision 253486)
+++ gcc/tree-data-ref.c (working copy)
@@ -1207,35 +1207,22 @@ data_ref_compare_tree (tree t1, tree t2)
if (t2 == NULL)
return 1;
- STRIP_NOPS (t1);
- STRIP_NOPS (t2);
+ STRIP_USELESS_TYPE_CONVERSION (t1);
+ STRIP_USELESS_TYPE_CONVERSION (t2);
+ if (t1 == t2)
+ return 0;
- if (TREE_CODE (t1) != TREE_CODE (t2))
+ if (TREE_CODE (t1) != TREE_CODE (t2)
+ && CONVERT_EXPR_P (t1) != CONVERT_EXPR_P (t2))
return TREE_CODE (t1) < TREE_CODE (t2) ? -1 : 1;
code = TREE_CODE (t1);
switch (code)
{
- /* For const values, we can just use hash values for comparisons. */
case INTEGER_CST:
- case REAL_CST:
- case FIXED_CST:
- case STRING_CST:
- case COMPLEX_CST:
- case VECTOR_CST:
- {
- hashval_t h1 = iterative_hash_expr (t1, 0);
- hashval_t h2 = iterative_hash_expr (t2, 0);
- if (h1 != h2)
- return h1 < h2 ? -1 : 1;
- break;
- }
+ return tree_int_cst_compare (t1, t2);
case SSA_NAME:
- cmp = data_ref_compare_tree (SSA_NAME_VAR (t1), SSA_NAME_VAR (t2));
- if (cmp != 0)
- return cmp;
-
if (SSA_NAME_VERSION (t1) != SSA_NAME_VERSION (t2))
return SSA_NAME_VERSION (t1) < SSA_NAME_VERSION (t2) ? -1 : 1;
break;
@@ -1243,22 +1230,26 @@ data_ref_compare_tree (tree t1, tree t2)
default:
tclass = TREE_CODE_CLASS (code);
- /* For var-decl, we could compare their UIDs. */
+ /* For decls, compare their UIDs. */
if (tclass == tcc_declaration)
{
if (DECL_UID (t1) != DECL_UID (t2))
return DECL_UID (t1) < DECL_UID (t2) ? -1 : 1;
break;
}
-
- /* For expressions with operands, compare their operands recursively. */
- for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
+ /* For expressions, compare their operands recursively. */
+ else if (IS_EXPR_CODE_CLASS (tclass))
{
- cmp = data_ref_compare_tree (TREE_OPERAND (t1, i),
- TREE_OPERAND (t2, i));
- if (cmp != 0)
- return cmp;
+ for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
+ {
+ cmp = data_ref_compare_tree (TREE_OPERAND (t1, i),
+ TREE_OPERAND (t2, i));
+ if (cmp != 0)
+ return cmp;
+ }
}
+ else
+ gcc_unreachable ();
}
return 0;