On October 3, 2017 1:55:35 PM GMT+02:00, Jakub Jelinek <ja...@redhat.com> wrote:
>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?
OK.
Richard.
>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
