Re: [PATCH] tree-sra: fix compare_access_positions qsort comparator

[Martin Jambor <mjambor at suse dot cz>]

On Thu, Sep 21, 2017 at 08:27:31PM +0300, Alexander Monakov wrote:
> Hi,
> 
> The compare_access_positions qsort comparator lacks transitivity, although
> somewhat surprisingly this issue didn't manifest on 64-bit x86 bootstraps.
> The first invalid comparison step is here (tree-sra.c:1545):
> 
>       /* Put the integral type with the bigger precision first.  */
>       else if (INTEGRAL_TYPE_P (f1->type)
> 	       && INTEGRAL_TYPE_P (f2->type))
> 	return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
> 
> Imagine you have items A, B, C such that they compare equal according to
> preceding comparison steps, A and C are integral and have precision 64 resp.
> 32, B is non-integral.  Then you have C < A according to this step, but
> comparisons against B depend on TYPE_UID, so you can end up with A < B < C < A.
> 
> A minimal fix would be to order all integral items before/after non-integral,
> like preceding code already does for aggregate/vector/complex types.

Thanks for spotting this.  Nevertheless, I would prefer SRA to select
integer types over non-integer ones (i.e. floats), because in the
common scenario which is a union of a float and an int, the int is the
type for which we can enable more subsequent optimizations, even if it
means that we do not scalarize some exotic cases.  So I'm currently
testing the following (if we ever find that this is a problem in
practice, we can fix it at the cost of making
sort_and_splice_var_accesses more complicated but capable of undoing
this decision).

By the way, after I jettison IPA-SRA from tree-sra.c, I'll start
reworking it in a way that does not have the qsort in it.

Thanks again,

Martin

diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index 163b7a2d03b..0f92033d0bb 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -1542,19 +1542,20 @@ compare_access_positions (const void *a, const void *b)
 	       && TREE_CODE (f2->type) != COMPLEX_TYPE
 	       && TREE_CODE (f2->type) != VECTOR_TYPE)
 	return -1;
-      /* Put the integral type with the bigger precision first.  */
+      /* Put any integral type before any non-integral type.  When splicing, we
+	 make sure that those with insufficient precision and occupupying the
+	 same space are not scalarized.  */
       else if (INTEGRAL_TYPE_P (f1->type)
+	       && !INTEGRAL_TYPE_P (f2->type))
+	return -1;
+      else if (!INTEGRAL_TYPE_P (f1->type)
 	       && INTEGRAL_TYPE_P (f2->type))
-	return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
-      /* Put any integral type with non-full precision last.  */
-      else if (INTEGRAL_TYPE_P (f1->type)
-	       && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type))
-		   != TYPE_PRECISION (f1->type)))
 	return 1;
-      else if (INTEGRAL_TYPE_P (f2->type)
-	       && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type))
-		   != TYPE_PRECISION (f2->type)))
-	return -1;
+      /* Put the integral type with the bigger precision first.  */
+      else if (INTEGRAL_TYPE_P (f1->type)
+	       && INTEGRAL_TYPE_P (f2->type)
+	       && (TYPE_PRECISION (f2->type) != TYPE_PRECISION (f1->type)))
+	return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type);
       /* Stabilize the sort.  */
       return TYPE_UID (f1->type) - TYPE_UID (f2->type);
     }
@@ -2055,6 +2056,9 @@ sort_and_splice_var_accesses (tree var)
       bool grp_partial_lhs = access->grp_partial_lhs;
       bool first_scalar = is_gimple_reg_type (access->type);
       bool unscalarizable_region = access->grp_unscalarizable_region;
+      bool non_full_precision = (INTEGRAL_TYPE_P (access->type)
+				 && (TREE_INT_CST_LOW (TYPE_SIZE (access->type))
+				     != TYPE_PRECISION (access->type)));
 
       if (first || access->offset >= high)
 	{
@@ -2102,6 +2106,21 @@ sort_and_splice_var_accesses (tree var)
 	     this combination of size and offset, the comparison function
 	     should have put the scalars first.  */
 	  gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type));
+	  /* It also prefers integral types to non-integral.  However, when the
+	     precision of the selected type does not span the entire area and
+	     should also be used for a non-integer (i.e. float), we must not
+	     let that happen.  */
+	  if (non_full_precision && !INTEGRAL_TYPE_P (ac2->type))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "Cannot sclarize the following access "
+			   "because insufficient precision integer type was "
+			   "selected.\n  ");
+		  dump_access (dump_file, access, false);
+		}
+	      unscalarizable_region = true;
+	    }
 	  ac2->group_representative = access;
 	  j++;
 	}