Re: [PATCH] Make CSE path following use the CFG

[Ian Lance Taylor <iant at google dot com>]

Steven Bosscher <stevenb.gcc@gmail.com> writes:

> This is the patch to make CSE path following use the control flow
> graph to determine the path to follow.  This is really a pretty
> straight-forward change, but there are a few caveats:
> * Without -fcse-follow-jumps, CSE is now purely a local pass.  It
>   is easy to revert this to the current behavior, but the change
>   is deliberate: It gives a rather nice speedup at -O1, and most
>   of the things that CSE does are local anyway so the effect on
>   the generated code is not that large.

You know we're going to ask this: can you characterize "not that
large?"  It's not a critical point, since -O2 enables
-fcse-follow-jumps, but it's still worth mentioning.

> +   DATA is a pointer to a struct cse_basic_blockb_data, that is used to
> +   describe the path.

Typo in the struct name.

> +	  /* If we previously followed a path along the branch edge, try
> +	     the falltrhu edge now.  */

Typo for "fallthru".

> +	  /* A PARALLEL can have lots of SETs in it,
> +	     especially if it is really an ASM_OPERANDS.  */
> +	  if (GET_CODE (PATTERN (insn)) == PARALLEL)
> +	    nsets += XVECLEN (PATTERN (insn), 0);
> +	  else
> +	    nsets += 1;

Hmmm, I kind of think the name "nsets" should change to something like
"max_sets".  But this is an existing name with similar semantics, so
don't change it in this patch.

> +	  /* If we have processed 1,000 insns, flush the hash table to
> +	     avoid extreme quadratic behavior.  We must not include NOTEs
> +	     in the count since there may be more of them when generating
> +	     debugging information.  If we clear the table at different
> +	     times, code generated with -g -O might be different than code
> +	     generated with -O but not -g.
> +
> +	     FIXME: This is a real kludge and needs to be done some other
> +		    way.  */
> +	  if (!INSN_P (insn)
> +	      && num_insns++ > PARAM_VALUE (PARAM_MAX_CSE_INSNS))
> +	    {
> +	      flush_hash_table ();
> +	      num_insns = 0;
> +	    }

That condition is wrong: you need to check INSN_P (insn), not !INSN_P
(insn).

> +      /* If we changed a conditional jump, we may have terminated
> +	 the path we are following.  Check that by verifying that
> +	 the edge we would take still exists.  If the edge does
> +	 not exist anymore, purge the remainder of the path.
> +	 Note that this will cause us to return to the caller.  */
> +      if (path_entry < path_size - 1)
> +	{
> +	  basic_block next_bb = ebb_data->path[path_entry + 1].bb;
> +	  if (!find_edge (bb, next_bb))
> +	    {
> +	      do
> +		{
> +		  ebb_data->path[--path_size].bb = NULL;
> +		}
> +	      while (ebb_data->path[path_size - 1].bb != bb);
> +	      ebb_data->path_size = path_size;

Isn't the do/while condition effectively the same as (path_size - 1 !=
path_entry)?  And is it important to set the entries in the path[]
array to NULL?  Why not replace the loop with "path_size = path_entry
+ 1"?

> +	  /* If this basic block was already processed or has no sets,
> +	     skip it.  */
> +	  if (ebb_data.nsets == 0)
> +	    continue;

Is that comment right?  I don't see any test of "this basic block was
already processed."  That was tested above.

> +	  /* Get a reasonable extimate for the maximum number of qty's
> +	     needed for this path.  For this, we take the number of sets
> +	     and multiply that by MAX_RECOG_OPERANDS.
> +	     The old CSE path following code would use MAX(2*nsets,500)
> +	     but now that we know exactly how many insns (and hence sets)
> +	     we will see in the path, it seemed like a good idea to just
> +	     use max_qty = 2 * nsets.  Interestingly, we end up writing
> +	     past the end of qty_table with that value for max_qty.  In
> +	     other words, this was a latent bug in cse.c present since 
> +	     at least 1992.
> +	     Oh well, we just take a bigger max_qty now to play safe.  */

I would remove all of this comment after the first two sentences.
It's a bit unclear, and I don't think it is useful.


You're going to need to retest because of the incorrect negation of
INSN_P.  Please change the do/while loop if my suggestions look
correct.  Please fix the comments.

I will preapprove the patch with those changes if testing passes.  But
please wait a few days before checking it in in case anybody else has
any comments.

Thanks for tackling this.

Ian