On Mon, 9 Oct 2017, Richard Biener wrote:
> On Sat, 7 Oct 2017, Richard Sandiford wrote:
>
> > Richard Biener <rguent...@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 <rguent...@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.
And this is what I have applied.
Bootstrapped and tested on x86_64-unknown-linux-gnu, SPEC CPU 2006 tested.
Richard.
2017-10-09 Richard Biener <rguent...@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,28 @@ 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:
+ return tree_int_cst_compare (t1, t2);
+
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;
- }
+ if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
+ return TREE_STRING_LENGTH (t1) < TREE_STRING_LENGTH (t2) ? -1 : 1;
+ return memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
+ TREE_STRING_LENGTH (t1));
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 +1236,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;
