Fix sort_by_operand_rank with qsort checking (PR tree-optimization/82381, #2)

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  <jakub@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.



	Jakub

On October 3, 2017 1:55:35 PM GMT+02:00, Jakub Jelinek <jakub@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  <jakub@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