Optimize BB sorting in domwalk

On Mon, 24 Jul 2017, Jeff Law wrote:
> As Uli noted, we should be using std::swap.
> 
> Can you please repost ?

	* 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(-)

On Tue, Jul 25, 2017 at 10:22 AM, Alexander Monakov <amonakov@ispras.ru> wrote:
> On Mon, 24 Jul 2017, Jeff Law wrote:
>> As Uli noted, we should be using std::swap.
>>
>> Can you please repost ?
>
>         * domwalk.c (cmp_bb_postorder): Simplify.
>         (sort_bbs_postorder): New function.  Use it...
>         (dom_walker::walk): ...here to optimize common cases.

Ok.  Note that I think vec::qsort might benefit from handling length
() == 2 and domwalk
might benefit from using vec::qsort if it would work on a sub-vector
as we are asking for
here...

Richard.

> ---
>  gcc/domwalk.c | 53 ++++++++++++++++++++++++++++++++++++-----------------
>  1 file changed, 36 insertions(+), 17 deletions(-)
>
> diff --git a/gcc/domwalk.c b/gcc/domwalk.c
> index a0daae6b2d8..df51b8c4451 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 bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2];
> +      if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
> +       std::swap (bb0, bb1);
> +      if (bb_postorder[bb1->index] < bb_postorder[bb2->index])
> +       {
> +         std::swap (bb1, bb2);
> +         if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
> +           std::swap (bb0, bb1);
> +       }
> +      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])
> --
> 2.13.3

On Tue, 25 Jul 2017, Alexander Monakov wrote:
> --- 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);

Actually since the 'int *bb_postorder' array is not going to hold negative
entries, this can be simply

  return n2 - n1;

(the (A > B) - (A < B) formulation is useful in case signed A - B may overflow)

Alexander