On Tue, Jul 25, 2017 at 10:22 AM, Alexander Monakov <[email protected]> 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
