Fix overflows in -fprofile-reorder-functions

[Alexander Monakov]

2On Sun, 8 Dec 2019, Jan Hubicka wrote:

> Other explanation would be that our new qsort with broken comparator due to
> overflow can actualy remove some entries in the array, but that sounds bit
> crazy.

gcc_qsort only reorders elements, making it possible for gcc_qsort_chk (that
runs afterwards) to catch crazy comparators in a sound manner.

> Bootstrapped/regested x86_64-linux. Comitted.

I have a few comments, please see below.

> --- cgraphunit.c	(revision 279076)
> +++ cgraphunit.c	(working copy)
> @@ -2359,19 +2359,33 @@ cgraph_node::expand (void)
>  /* Node comparator that is responsible for the order that corresponds
>     to time when a function was launched for the first time.  */
>  
> -static int
> -node_cmp (const void *pa, const void *pb)
> +int
> +tp_first_run_node_cmp (const void *pa, const void *pb)
>  {
>    const cgraph_node *a = *(const cgraph_node * const *) pa;
>    const cgraph_node *b = *(const cgraph_node * const *) pb;
> +  gcov_type tp_first_run_a = a->tp_first_run;
> +  gcov_type tp_first_run_b = b->tp_first_run;
> +
> +  if (!opt_for_fn (a->decl, flag_profile_reorder_functions)
> +      || a->no_reorder)
> +    tp_first_run_a = 0;
> +  if (!opt_for_fn (b->decl, flag_profile_reorder_functions)
> +      || b->no_reorder)
> +    tp_first_run_b = 0;
> +
> +  if (tp_first_run_a == tp_first_run_b)
> +    return b->order - a->order;
>  
>    /* Functions with time profile must be before these without profile.  */
> -  if (!a->tp_first_run || !b->tp_first_run)
> -    return a->tp_first_run - b->tp_first_run;
> +  if (!tp_first_run_a || !tp_first_run_b)
> +    return tp_first_run_a ? 1 : -1;

The code does the opposite of the comment: when tp_first_run_b is 0, it will
return 1, indicating a > b, causing b to appear in front of a in the sorted
array.

I would recommend to make these variables uint64_t, then you can simply do

  tp_first_run_a--;
  tp_first_run_b--;

making 0 wrap around to UINT64_MAX. Then they will naturally sort after all
other nodes.

> -  return a->tp_first_run != b->tp_first_run
> -	 ? b->tp_first_run - a->tp_first_run
> -	 : b->order - a->order;
> +  /* Watch for overlflow - tp_first_run is 64bit.  */
> +  if (tp_first_run_a > tp_first_run_b)
> +    return -1;
> +  else
> +    return 1;

This also sorts in the reverse order -- please fix the comments if that's really
intended.

> +  /* Output functions in RPO so callers get optimized before callees.  This
> +     makes ipa-ra and other propagators to work.
> +     FIXME: This is far from optimal code layout.  */

I think this should have said "callees get optimized before callers".


Thanks.
Alexander