Re: [PATCH 2/4] bb-reorder: Add the "simple" algorithm

[Bernd Schmidt <bschmidt@redhat.com>]

On 09/24/2015 12:06 AM, Segher Boessenkool wrote:
> This is the meat of this series: a new algorithm to do basic block
> reordering.  It uses the simple greedy approach to maximum weighted
> matching, where the weights are the predicted execution frequency of
> the edges.  This always finds a solution that is within a factor two
> of optimal, if you disregard loops (which we cannot allow) and the
> complications of block partitioning.

Looks really good for the most part.

The comment at the top of the file should be updated to mention both 
algorithms.

> +  /* Sort the edges, the most desirable first.  */
> +
> +  std::stable_sort (edges, edges + n, edge_order);

Any thoughts on this vs qsort? Do you need a stable sort?

> +  int j;
> +  for (j = 0; j < n; j++)

for (int j ...
here and in the other loop that uses j.

> +  /* If the entry edge no longer falls through we have to make a new
> +     block so it can do so again.  */
> +
> +  edge e = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
> +  if (e->dest != ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux)
> +    {
> +      force_nonfallthru (e);
> +      e->src->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
> +      BB_COPY_PARTITION (e->src, e->dest);
> +    }
> +}

That's a bit odd, can this situation be prevented earlier? Why wouldn't 
we force the entry edge to fall thru?


Bernd