vec.h (vec::sort): Add gcc_qsort_r support.

2019-08-02  Richard Biener  <rguenther@suse.de>

	* vec.h (vec::sort): Add gcc_qsort_r support.
	(vec::bsearch): Add an overload with gcc_qsort_r style callbacks.
	* tree-ssa-loop-im.c (sort_bbs_in_loop_postorder_cmp): Adjust
	to gcc_qsort_r style callback.
	(sort_locs_in_loop_postorder_cmp): Likewise.
	(analyze_memory_references): Use gcc_sort_r interfaces.
	(find_ref_loc_in_loop_cmp): Use new bsearch overload.

From-SVN: r274004

3 files changed, 105 insertions, 8 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 096716a..c0e3cd8 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2019-08-02  Richard Biener  <rguenther@suse.de>
+
+	* vec.h (vec::sort): Add gcc_qsort_r support.
+	(vec::bsearch): Add an overload with gcc_qsort_r style callbacks.
+	* tree-ssa-loop-im.c (sort_bbs_in_loop_postorder_cmp): Adjust
+	to gcc_qsort_r style callback.
+	(sort_locs_in_loop_postorder_cmp): Likewise.
+	(analyze_memory_references): Use gcc_sort_r interfaces.
+	(find_ref_loc_in_loop_cmp): Use new bsearch overload.
+
 2019-08-02  Martin Liska  <mliska@suse.cz>
 
 	PR lto/91313
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index 12176e0..e194a41 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -1579,8 +1579,10 @@ static unsigned *bb_loop_postorder;
 /* qsort sort function to sort blocks after their loop fathers postorder.  */
 
 static int
-sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
+sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_,
+				void *bb_loop_postorder_)
 {
+  unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
   basic_block bb1 = *(basic_block *)const_cast<void *>(bb1_);
   basic_block bb2 = *(basic_block *)const_cast<void *>(bb2_);
   class loop *loop1 = bb1->loop_father;
@@ -1593,8 +1595,10 @@ sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
 /* qsort sort function to sort ref locs after their loop fathers postorder.  */
 
 static int
-sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_)
+sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_,
+				 void *bb_loop_postorder_)
 {
+  unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
   mem_ref_loc *loc1 = (mem_ref_loc *)const_cast<void *>(loc1_);
   mem_ref_loc *loc2 = (mem_ref_loc *)const_cast<void *>(loc2_);
   class loop *loop1 = gimple_bb (loc1->stmt)->loop_father;
@@ -1622,7 +1626,8 @@ analyze_memory_references (void)
     if (bb->loop_father != current_loops->tree_root)
       bbs[i++] = bb;
   n = i;
-  qsort (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp);
+  gcc_sort_r (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp,
+	      bb_loop_postorder);
 
   /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
      That results in better locality for all the bitmaps.  */
@@ -1637,10 +1642,10 @@ analyze_memory_references (void)
      loop postorder number.  */
   im_mem_ref *ref;
   FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
-    ref->accesses_in_loop.qsort (sort_locs_in_loop_postorder_cmp);
+    ref->accesses_in_loop.sort (sort_locs_in_loop_postorder_cmp,
+				bb_loop_postorder);
 
   free (bbs);
-//  free (bb_loop_postorder);
 
   /* Propagate the information about accessed memory references up
      the loop hierarchy.  */
@@ -1700,8 +1705,10 @@ mem_refs_may_alias_p (im_mem_ref *mem1, im_mem_ref *mem2,
    in a loop.  */
 
 static int
-find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_)
+find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_,
+			  void *bb_loop_postorder_)
 {
+  unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
   class loop *loop = (class loop *)const_cast<void *>(loop_);
   mem_ref_loc *loc = (mem_ref_loc *)const_cast<void *>(loc_);
   class loop *loc_loop = gimple_bb (loc->stmt)->loop_father;
@@ -1726,7 +1733,8 @@ for_all_locs_in_loop (class loop *loop, im_mem_ref *ref, FN fn)
 
   /* Search for the cluster of locs in the accesses_in_loop vector
      which is sorted after postorder index of the loop father.  */
-  loc = ref->accesses_in_loop.bsearch (loop, find_ref_loc_in_loop_cmp);
+  loc = ref->accesses_in_loop.bsearch (loop, find_ref_loc_in_loop_cmp,
+				       bb_loop_postorder);
   if (!loc)
     return false;
 
diff --git a/gcc/vec.h b/gcc/vec.h
index 2dbf307..091056b 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -593,7 +593,10 @@ public:
   void unordered_remove (unsigned);
   void block_remove (unsigned, unsigned);
   void qsort (int (*) (const void *, const void *));
+  void sort (int (*) (const void *, const void *, void *), void *);
   T *bsearch (const void *key, int (*compar)(const void *, const void *));
+  T *bsearch (const void *key,
+	      int (*compar)(const void *, const void *, void *), void *);
   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
   bool contains (const T &search) const;
   static size_t embedded_size (unsigned);
@@ -1111,7 +1114,19 @@ inline void
 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
 {
   if (length () > 1)
-    ::qsort (address (), length (), sizeof (T), cmp);
+    gcc_qsort (address (), length (), sizeof (T), cmp);
+}
+
+/* Sort the contents of this vector with qsort.  CMP is the comparison
+   function to pass to qsort.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
+			   void *data)
+{
+  if (length () > 1)
+    gcc_sort_r (address (), length (), sizeof (T), cmp, data);
 }
 
 
@@ -1149,6 +1164,41 @@ vec<T, A, vl_embed>::bsearch (const void *key,
   return NULL;
 }
 
+/* Search the contents of the sorted vector with a binary search.
+   CMP is the comparison function to pass to bsearch.  */
+
+template<typename T, typename A>
+inline T *
+vec<T, A, vl_embed>::bsearch (const void *key,
+			      int (*compar) (const void *, const void *,
+					     void *), void *data)
+{
+  const void *base = this->address ();
+  size_t nmemb = this->length ();
+  size_t size = sizeof (T);
+  /* The following is a copy of glibc stdlib-bsearch.h.  */
+  size_t l, u, idx;
+  const void *p;
+  int comparison;
+
+  l = 0;
+  u = nmemb;
+  while (l < u)
+    {
+      idx = (l + u) / 2;
+      p = (const void *) (((const char *) base) + (idx * size));
+      comparison = (*compar) (key, p, data);
+      if (comparison < 0)
+	u = idx;
+      else if (comparison > 0)
+	l = idx + 1;
+      else
+	return (T *)const_cast<void *>(p);
+    }
+
+  return NULL;
+}
+
 /* Return true if SEARCH is an element of V.  Note that this is O(N) in the
    size of the vector and so should be used with care.  */
 
@@ -1401,7 +1451,10 @@ public:
   void unordered_remove (unsigned);
   void block_remove (unsigned, unsigned);
   void qsort (int (*) (const void *, const void *));
+  void sort (int (*) (const void *, const void *, void *), void *);
   T *bsearch (const void *key, int (*compar)(const void *, const void *));
+  T *bsearch (const void *key,
+	      int (*compar)(const void *, const void *, void *), void *);
   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
   bool contains (const T &search) const;
   void reverse (void);
@@ -1898,6 +1951,18 @@ vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
     m_vec->qsort (cmp);
 }
 
+/* Sort the contents of this vector with qsort.  CMP is the comparison
+   function to pass to qsort.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::sort (int (*cmp) (const void *, const void *,
+					   void *), void *data)
+{
+  if (m_vec)
+    m_vec->sort (cmp, data);
+}
+
 
 /* Search the contents of the sorted vector with a binary search.
    CMP is the comparison function to pass to bsearch.  */
@@ -1912,6 +1977,20 @@ vec<T, va_heap, vl_ptr>::bsearch (const void *key,
   return NULL;
 }
 
+/* Search the contents of the sorted vector with a binary search.
+   CMP is the comparison function to pass to bsearch.  */
+
+template<typename T>
+inline T *
+vec<T, va_heap, vl_ptr>::bsearch (const void *key,
+				  int (*cmp) (const void *, const void *,
+					      void *), void *data)
+{
+  if (m_vec)
+    return m_vec->bsearch (key, cmp, data);
+  return NULL;
+}
+
 
 /* Find and return the first position in which OBJ could be inserted
    without changing the ordering of this vector.  LESSTHAN is a