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
