On Tue, Oct 03, 2017 at 01:24:32PM +0300, Alexander Monakov wrote:
> On Tue, 3 Oct 2017, Jakub Jelinek wrote:
> > The qsort cmp transitivity checks may fail with the sort_by_operand_rank
> > comparator, because if one of the operands has stmt_to_insert and the
> > other doesn't (but likely also if one SSA_NAME is (D) and the other is not),
> > we fallthrough into SSA_NAME_VERSION comparison, but if both aren't (D) and
> > both don't have stmt_to_insert, we use different comparison rules.
>
> When looking at the code I've noticed another issue, so the fix seems
> incomplete (but I don't know if the other problem can/should be fixed
> independently), see below:
>
>
> > --- gcc/tree-ssa-reassoc.c.jj 2017-10-02 17:33:14.270282226 +0200
> > +++ gcc/tree-ssa-reassoc.c 2017-10-02 18:18:07.328611132 +0200
> > @@ -514,36 +514,37 @@ sort_by_operand_rank (const void *pa, co
> > && TREE_CODE (oea->op) == SSA_NAME
> > && TREE_CODE (oeb->op) == SSA_NAME)
> > {
>
> The containing if statement condition reads:
>
> if (oeb->rank == oea->rank
> && TREE_CODE (oea->op) == SSA_NAME
> && TREE_CODE (oeb->op) == SSA_NAME)
>
> so as far as I can tell it's possible to have items A, B, C such that
> all have same rank, A and C correspond to SSA_NAMEs and compare C < A,
> but B does not, so comparisons of A or C against B fall down to
>
> return oeb->id > oea->id ? 1 : -1;
>
> and ultimately result in A < B < C < A.
I think it is likely only hypothetical, because get_rank for non-SSA_NAME
should be 0 and thus handled earlier (for SSA_NAME I think rank of 0 is
still possible).
That said, this untested patch reshuffles stuff a little bit, ok for trunk
if it passes testing?
2017-10-03 Jakub Jelinek <ja...@redhat.com>
PR tree-optimization/82381
* tree-ssa-reassoc.c (sort_by_operand_rank): Check for different
oeN->rank first. Return 1 or -1 if one op is SSA_NAME and the other
is not.
--- gcc/tree-ssa-reassoc.c.jj 2017-10-03 13:24:00.000000000 +0200
+++ gcc/tree-ssa-reassoc.c 2017-10-03 13:41:23.098183270 +0200
@@ -495,10 +495,13 @@ sort_by_operand_rank (const void *pa, co
const operand_entry *oea = *(const operand_entry *const *)pa;
const operand_entry *oeb = *(const operand_entry *const *)pb;
+ if (oeb->rank != oea->rank)
+ return oeb->rank > oea->rank ? 1 : -1;
+
/* It's nicer for optimize_expression if constants that are likely
- to fold when added/multiplied//whatever are put next to each
+ to fold when added/multiplied/whatever are put next to each
other. Since all constants have rank 0, order them by type. */
- if (oeb->rank == 0 && oea->rank == 0)
+ if (oea->rank == 0)
{
if (constant_type (oeb->op) != constant_type (oea->op))
return constant_type (oeb->op) - constant_type (oea->op);
@@ -508,51 +511,50 @@ sort_by_operand_rank (const void *pa, co
return oeb->id > oea->id ? 1 : -1;
}
+ if (TREE_CODE (oea->op) != SSA_NAME)
+ {
+ if (TREE_CODE (oeb->op) != SSA_NAME)
+ return oeb->id > oea->id ? 1 : -1;
+ else
+ return 1;
+ }
+ else if (TREE_CODE (oeb->op) != SSA_NAME)
+ return -1;
+
/* Lastly, make sure the versions that are the same go next to each
other. */
- if (oeb->rank == oea->rank
- && TREE_CODE (oea->op) == SSA_NAME
- && TREE_CODE (oeb->op) == SSA_NAME)
+ if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
{
- if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
+ /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse
+ versions of removed SSA_NAMEs, so if possible, prefer to sort
+ based on basic block and gimple_uid of the SSA_NAME_DEF_STMT.
+ See PR60418. */
+ gimple *stmta = SSA_NAME_DEF_STMT (oea->op);
+ gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op);
+ basic_block bba = gimple_bb (stmta);
+ basic_block bbb = gimple_bb (stmtb);
+ if (bbb != bba)
{
- /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse
- versions of removed SSA_NAMEs, so if possible, prefer to sort
- based on basic block and gimple_uid of the SSA_NAME_DEF_STMT.
- See PR60418. */
- gimple *stmta = SSA_NAME_DEF_STMT (oea->op);
- gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op);
- basic_block bba = gimple_bb (stmta);
- basic_block bbb = gimple_bb (stmtb);
- if (bbb != bba)
- {
- /* One of the SSA_NAMEs can be defined in oeN->stmt_to_insert
- but the other might not. */
- if (!bba)
- return 1;
- if (!bbb)
- return -1;
- /* If neither is, compare bb_rank. */
- if (bb_rank[bbb->index] != bb_rank[bba->index])
- return bb_rank[bbb->index] - bb_rank[bba->index];
- }
-
- bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
- bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta);
- if (da != db)
- return da ? 1 : -1;
-
- return (SSA_NAME_VERSION (oeb->op) > SSA_NAME_VERSION (oea->op)
- ? 1 : -1);
+ /* One of the SSA_NAMEs can be defined in oeN->stmt_to_insert
+ but the other might not. */
+ if (!bba)
+ return 1;
+ if (!bbb)
+ return -1;
+ /* If neither is, compare bb_rank. */
+ if (bb_rank[bbb->index] != bb_rank[bba->index])
+ return bb_rank[bbb->index] - bb_rank[bba->index];
}
- else
- return oeb->id > oea->id ? 1 : -1;
+
+ bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
+ bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta);
+ if (da != db)
+ return da ? 1 : -1;
+
+ return SSA_NAME_VERSION (oeb->op) > SSA_NAME_VERSION (oea->op) ? 1 : -1;
}
- if (oeb->rank != oea->rank)
- return oeb->rank > oea->rank ? 1 : -1;
- else
- return oeb->id > oea->id ? 1 : -1;
+ return oeb->id > oea->id ? 1 : -1;
}
/* Add an operand entry to *OPS for the tree operand OP. */
Jakub
