[PATCH] Optimize BB sorting in domwalk

[Alexander Monakov <amonakov at ispras dot ru>]

Profiling uses of qsort in GCC reveals that a significant portion of calls
comes from domwalk.c where child nodes in dominator tree are reordered
according to postorder numbering.  However we know that in dominator trees
the vast majority of nodes have 0, 2 or 3 children, and handling those
cases separately allows to avoid qsort overhead.

I don't have trunk figures handy, but on gcc-6 release-checking tramp3d
compilation this would eliminate about 63% of _all_ qsort calls by count,
or about 27% by time.  Call count profile looks like:

N=0	N=1	N=2	N=3	N=4	N=5	N=6 	...	Total
16111   9406    228607  91870   20154   8317    3823            406971

With this patch it would look like

N=0	N=1	N=2	N=3	N=4	N=5	N=6	...	Total
16111   9406    32200   34132   16966   8022    3702            149177

While at it, I've also added a clarifying comment to bb_postorder (it
actually gives reverse postorder), simplified casts in cmp_bb_postorder
and changed it to compute the result in a branchless fashion.

Bootstrapped and regtested on x86-64, also verified that gcc/*.o files are
unchanged except for domwalk.o and *-checksum.o.  OK for trunk?

	* domwalk.c (cmp_bb_postorder): Simplify.
	(sort_bbs_postorder): New function.  Use it...
	(dom_walker::walk): ...here to optimize common cases.
---
 gcc/domwalk.c | 53 ++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 36 insertions(+), 17 deletions(-)

diff --git a/gcc/domwalk.c b/gcc/domwalk.c
index a0daae6..dfb1993 100644
--- a/gcc/domwalk.c
+++ b/gcc/domwalk.c
@@ -128,19 +128,46 @@ along with GCC; see the file COPYING3.  If not see
     which is currently an abstraction over walking tree statements.  Thus
     the dominator walker is currently only useful for trees.  */
 
+/* Reverse postorder index of each basic block.  */
 static int *bb_postorder;
 
 static int
 cmp_bb_postorder (const void *a, const void *b)
 {
-  basic_block bb1 = *(basic_block *)const_cast<void *>(a);
-  basic_block bb2 = *(basic_block *)const_cast<void *>(b);
-  if (bb1->index == bb2->index)
-    return 0;
+  basic_block bb1 = *(const basic_block *)(a);
+  basic_block bb2 = *(const basic_block *)(b);
+  int n1 = bb_postorder[bb1->index], n2 = bb_postorder[bb2->index];
   /* Place higher completion number first (pop off lower number first).  */
-  if (bb_postorder[bb1->index] > bb_postorder[bb2->index])
-    return -1;
-  return 1;
+  return (n1 < n2) - (n1 > n2);
+}
+
+/* Permute array BBS of N basic blocks in postorder,
+   i.e. by descending number in BB_POSTORDER array.  */
+
+static void
+sort_bbs_postorder (basic_block *bbs, int n)
+{
+  if (__builtin_expect (n == 2, true))
+    {
+      basic_block bb0 = bbs[0], bb1 = bbs[1];
+      if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
+	bbs[0] = bb1, bbs[1] = bb0;
+    }
+  else if (__builtin_expect (n == 3, true))
+    {
+      basic_block t, bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2];
+      if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
+	t = bb0, bb0 = bb1, bb1 = t;
+      if (bb_postorder[bb1->index] < bb_postorder[bb2->index])
+	{
+	  t = bb1, bb1 = bb2, bb2 = t;
+	  if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
+	    t = bb0, bb0 = bb1, bb1 = t;
+	}
+      bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
+    }
+  else
+    qsort (bbs, n, sizeof *bbs, cmp_bb_postorder);
 }
 
 /* Constructor for a dom walker.
@@ -284,16 +311,8 @@ dom_walker::walk (basic_block bb)
 	  for (dest = first_dom_son (m_dom_direction, bb);
 	       dest; dest = next_dom_son (m_dom_direction, dest))
 	    worklist[sp++] = dest;
-	  if (m_dom_direction == CDI_DOMINATORS)
-	    switch (sp - saved_sp)
-	      {
-	      case 0:
-	      case 1:
-		break;
-	      default:
-		qsort (&worklist[saved_sp], sp - saved_sp,
-		       sizeof (basic_block), cmp_bb_postorder);
-	      }
+	  if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS)
+	    sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp);
 	}
       /* NULL is used to mark pop operations in the recursion stack.  */
       while (sp > 0 && !worklist[sp - 1])
-- 
1.8.3.1