[PATCH] Add qsort comparator consistency checking (PR71702)

[Alexander Monakov <amonakov at ispras dot ru>]

Hi,

this patch adds internal checking for comparator functions that GCC passes to
qsort.  PR71702 describes an ICE that happens because comparator
'dr_group_sort_cmp' used to be non-transitive in some cases until GCC 6.  This
patch would uncover that issue on a number of small testcases in GCC's
testsuite, so it should be useful to catch similar issues in the future as well.

Although the meat of the implementation is not tied to vec<>, this patch adds
verification only to vec::qsort.  I see there's a number of other ::qsort uses
in GCC; it should be useful to have such checking there as well.  I'd appreciate
input on that (I'd go with '#define qsort(b, n, s, c) qsort_chk (b, n, s, c)'
in system.h and implement qsort_chk as a checking wrapper around libc qsort).

Bootstrapped and regtested on x86_64, OK to apply?

Alexander

	* vec.c (vec_check_sort_cmp): New.  Use it...
	* vec.h (vec<T, A, vl_embed>::qsort): ...here to verify comparator
	consistency when checking is enabled.

diff --git a/gcc/vec.c b/gcc/vec.c
index fd200ea..b4ac0b4 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -190,6 +190,44 @@ dump_vec_loc_statistics (void)
   vec_mem_desc.dump (VEC_ORIGIN);
 }
 
+/* Verify consistency of comparator CMP on array BASE of N SIZE-sized elements.
+   Assuming the array should be sorted according to CMP, any assertion failure
+   here implies that CMP is not transitive, or is not anti-commutative.  */
+
+void
+vec_check_sort_cmp (const void *base, size_t n, size_t size,
+		    int (*cmp) (const void *, const void *))
+{
+  const char *cbase = (const char *) base;
+  size_t i1, i2, i, j;
+  /* The following loop nest has O(n^2) time complexity.  Limit n to avoid
+     slowness on artificial testcases.  */
+  if (n > 100)
+    n = 100;
+#define CMP(i, j) cmp (cbase + (i) * size, cbase + (j) * size)
+  /* The outer loop iterates over maximum spans [i1, i2) such that elements
+     within each span compare equal.  */
+  for (i1 = 0; i1 < n; i1 = i2)
+    {
+      /* Position i2 past the last element that compares equal to i1'th.  */
+      for (i2 = i1 + 1; i2 < n; i2++)
+	if (CMP (i1, i2))
+	  break;
+	else
+	  gcc_assert (!CMP (i2, i1));
+      /* Verify that all remaining pairs within current span compare equal.  */
+      for (i = i1 + 1; i + 1 < i2; i++)
+	for (j = i + 1; j < i2; j++)
+	  gcc_assert (!CMP (i, j) && !CMP (j, i));
+      /* Verify that all elements within current span compare less than any
+         element beyond the span.  */
+      for (i = i1; i < i2; i++)
+	for (j = i2; j < n; j++)
+	  gcc_assert (CMP (i, j) < 0 && CMP (j, i) > 0);
+    }
+#undef CMP
+}
+
 #ifndef GENERATOR_FILE
 #if CHECKING_P
 
diff --git a/gcc/vec.h b/gcc/vec.h
index eb8c270..ff1e37e 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -182,6 +182,9 @@ extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
 /* Support function for statistics.  */
 extern void dump_vec_loc_statistics (void);
 
+extern void vec_check_sort_cmp (const void *, size_t, size_t,
+			        int (*) (const void *, const void *));
+
 /* Hashtable mapping vec addresses to descriptors.  */
 extern htab_t vec_mem_usage_hash;
 
@@ -947,8 +950,11 @@ template<typename T, typename A>
 inline void
 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
 {
-  if (length () > 1)
-    ::qsort (address (), length (), sizeof (T), cmp);
+  if (length () <= 1)
+    return;
+  ::qsort (address (), length (), sizeof (T), cmp);
+  if (CHECKING_P)
+    vec_check_sort_cmp (address (), length (), sizeof (T), cmp);
 }