[patch] tree-cfg.c: Speed up tree_try_redirect_by_replacing_jump.

[Jeffrey A Law]

On Tue, 2004-11-23 at 13:49 -0500, Kazu Hirata wrote:
> Hi,
> 
> Attached is a patch to speed up tree_try_redirect_by_replacing_jump.
> 
> tree_try_redirect_by_replacing_jump tries to redirect a conditional
> jump like COND_EXPR or SWITCH_PEXR by replacing it with an
> unconditonal jump, which is actually represented implicitly.
> 
> Note that we can remove a conditoinal jump only when we have exactly
> two outgoing edges.  If we have exactly one outgoing edge, we don't
> have any COND_EXPR or SWITCH_EXPR in the first place.  If we have
> three or more outgoing edges, redirecting one of them will give you at
> least two unique edges, meaning that we cannot still remove
> SWITCH_EXPR.
> 
> If we have exactly two outgoing edges, then the edge that we are not
> redirecting must have the same destination as the one  want to
> redirect an edge to.
> 
> The patch implements the idea above.
> 
> Note that the original implementation of the check "leaks" a case with
> only one outgoing edge, in which case TMP is NULL.  In other words,
> "if (tmp)" cannot catch this case, letting the control fall through
> even though we know we have to return NULL at the end.
> 
> Here is a timing in seconds for three runs of "./cc1 -quiet -O2
> -fomit-frame-pointer -o /dev/null insn-attrtab.i".
> 
>       original patched
> real:  135.841 134.840 (0.736% down)
> user:  133.496 132.788 (0.530% down)
> 
> Tested on i686-pc-linux-gnu.  OK to apply?
> 
> p.s.
> I could do the same on cfgrtl.c:try_redirect_by_replacing_jump, but
> doing so actually generated different assembly code, so I didn't mix
> that into this patch.
> 
> Kazu Hirata
> 
> 2004-11-23  Kazu Hirata  <kazu@cs.umass.edu>
> 
> 	* tree-cfg.c (tree_try_redirect_by_replacing_jump): Speed up
> 	by restricting to the case with two outgoing edges.
Approved.

If you're looking for something to speed up, you might look at
redirect_branch_edge and its handling jump vectors.  It's basically
the same problem we had to fix for SWITCH_EXPRs at the tree level.

Odds are you could use almost the exact same mechanisms.  The
only difference is we'd need to chain together LABEL_REFs
with the same underlying CODE_LABEL instead of CASE_LABEL_EXPRs
with the same underlying LABEL_DECLs.

If I had to guess, it's probably worth 1-2% on pr15524.

[ A second thing to investigate would be why we had any
  calls to this routine for pr15524 to begin with.  I was
  quite surprised to see it in the profile data as I
  expected everything to have been threaded at the tree
  level for the PR.  ]