This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH 4/4] bb-reorder: convert to gcc_stablesort
On Tue, Aug 28, 2018 at 11:22 AM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> This converts the use in bb-reorder. I had to get a little bit creative with
> the comparator as profile_count::operator> does not implement a strict weak
> order.
So the previously used comparator was invalid? I think your proposed one
warrants some comments. Maybe trade speed for some clearer code?
The comments on the operator<> implementations are odd as well:
/* Comparsions are three-state and conservative. False is returned if
the inequality can not be decided. */
bool operator< (const profile_count &other) const
{
but bool can only represent a single state? Are you supposed to do
bool gt = count1 > count2;
bool le = count1 <= count2
if (!gt && !le)
/* unordered */;
else if (gt)
...
else if (le)
...
? And what do we want to do for the unordered case in bb-reorder?
Tie with current order, thus return zero?
Richard.
> * gcc/bb-reorder.c (edge_order): Convert to C-qsort-style
> tri-state comparator.
> (reorder_basic_blocks_simple): Change std::stable_sort to gcc_stablesort.
>
> diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
> index 57edde62c62..7c80609fbf4 100644
> --- a/gcc/bb-reorder.c
> +++ b/gcc/bb-reorder.c
> @@ -91,7 +91,6 @@
> */
>
> #include "config.h"
> -#define INCLUDE_ALGORITHM /* stable_sort */
> #include "system.h"
> #include "coretypes.h"
> #include "backend.h"
> @@ -2351,13 +2350,17 @@ reorder_basic_blocks_software_trace_cache (void)
> FREE (bbd);
> }
>
> -/* Return true if edge E1 is more desirable as a fallthrough edge than
> - edge E2 is. */
> +/* Order edges by execution frequency, higher first. */
>
> -static bool
> -edge_order (edge e1, edge e2)
> +static int
> +edge_order (const void *ve1, const void *ve2)
> {
> - return e1->count () > e2->count ();
> + edge e1 = *(const edge *) ve1;
> + edge e2 = *(const edge *) ve2;
> + profile_count c1 = e1->count ();
> + profile_count c2 = e2->count ();
> + profile_count m = c1.max (c2);
> + return (m == c2) - (m == c1);
> }
>
> /* Reorder basic blocks using the "simple" algorithm. This tries to
> @@ -2410,7 +2413,7 @@ reorder_basic_blocks_simple (void)
> all edges are equally desirable. */
>
> if (optimize_function_for_speed_p (cfun))
> - std::stable_sort (edges, edges + n, edge_order);
> + gcc_stablesort (edges, n, sizeof *edges, edge_order);
>
> /* Now decide which of those edges to make fallthrough edges. We set
> BB_VISITED if a block already has a fallthrough successor assigned
> --
> 2.13.3
>