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

Hi!

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.

The following patch fixes it, by doing all the checks unconditionally.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2017-10-03  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/82381
	* tree-ssa-reassoc.c (sort_by_operand_rank): Don't check
	stmt_to_insert nor wheather SSA_NAMEs are default defs.
	Return 1 or -1 if one of bba and bbb is NULL. If bb_rank is equal,
	fallthrough into reassoc_stmt_dominates_stmt_p.

	* gcc.c-torture/compile/pr82381.c: New test.


	Jakub

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.

Alexander

On October 3, 2017 12:00:21 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>Hi!
>
>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.
>
>The following patch fixes it, by doing all the checks unconditionally.
>Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK. Let's fix other things as followup. 

Richard. 

>2017-10-03  Jakub Jelinek  <jakub@redhat.com>
>
>	PR tree-optimization/82381
>	* tree-ssa-reassoc.c (sort_by_operand_rank): Don't check
>	stmt_to_insert nor wheather SSA_NAMEs are default defs.
>	Return 1 or -1 if one of bba and bbb is NULL. If bb_rank is equal,
>	fallthrough into reassoc_stmt_dominates_stmt_p.
>
>	* gcc.c-torture/compile/pr82381.c: New test.
>
>--- 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)
>     {
>-      /* 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.  */
>-      if (!SSA_NAME_IS_DEFAULT_DEF (oea->op)
>-	  && !SSA_NAME_IS_DEFAULT_DEF (oeb->op)
>-	  && !oea->stmt_to_insert
>-	  && !oeb->stmt_to_insert
>-	  && 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)
> 	    {
>+	      /* 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
>-	    {
>-	      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;
>-	    }
>-	}
> 
>-      if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
>-	return SSA_NAME_VERSION (oeb->op) > SSA_NAME_VERSION (oea->op) ? 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);
>+	}
>       else
> 	return oeb->id > oea->id ? 1 : -1;
>     }
>--- gcc/testsuite/gcc.c-torture/compile/pr82381.c.jj	2017-10-02
>18:13:51.532715601 +0200
>+++ gcc/testsuite/gcc.c-torture/compile/pr82381.c	2017-10-02
>18:13:51.532715601 +0200
>@@ -0,0 +1,18 @@
>+/* PR tree-optimization/82381 */
>+/* { dg-do compile } */
>+
>+signed char b, h;
>+unsigned short c, e;
>+short int d, f, g;
>+
>+void
>+foo ()
>+{
>+  if (h)
>+    {
>+      short a = -(d + c - b);
>+      f = e - a - -d;
>+    }
>+  if (c)
>+    g = 0;
>+}
>
>	Jakub