Re: [PATCH] Properly limit backwards label scanning in reorg.

[Richard Guenther <richard dot guenther at gmail dot com>]

On Sun, Oct 30, 2011 at 8:49 AM, David Miller <davem@davemloft.net> wrote:
>
> My check-gcc runs are completely dominated by the time it takes to
> test compile.exp=20001226-1.c
>
> On sparc when compiling this function at -O1 the lowest hanging fruit
> is some sillyness in reorg. ?It is trying to test a very specific
> condition within a well contained code block, but the label scanning
> is not constrained properly so things go haywire for large functions.
>
> Specifically it is looking at:
>
> ? ? ? ?INSN SEQ (delay_insn
> ? ? ? ? ? ? ? ? ?delay_slot_1
> ? ? ? ? ? ? ? ? ?...)
> ? ? ? ?...
> ? ? ? ?NEXT
> LABEL:
> ? ? ? ?next_active_insn (NEXT)
>
> and wants to scan backwards to find if LABEL exists, starting at
> next_active_insn (NEXT), and if so are NEXT and delay_slot_1 equal
> instructions (equal meaning rtx_equal_p()).
>
> But it just does a blind prev_label() call which will happily scan all
> the way to the beginning of the function. ?Compilation of this
> testcase at -O1 spends 1/3 of it's time in prev_insn ().
>
> In this specific reorg check, there is no reason to scan further back
> than INSN.
>
> So I've added a limited scanning helper function to reorg.c for this
> purpose and got rid of prev_insn entirely since there are no longer
> any users.
>
> Unfortunately, at -O2 this testcase causes exponential cost problems
> which are beyond my skills to fix. ?Specifically,
> tail_merge_optimize() applies it's clusters and
> iterate_fix_dominators() hits the worst case O(n) complexity of
> et_splay for a CFG structured like this. :-/ ?%38 of the compilation
> time is spent in et_splay().

Yeah, iteratively re-computing dominators can be expensive.  Tom,
can't you avoid that (thus, do you know how the dominance relation
changes?)

Richard.

> Committed to trunk.
>
> gcc/
>
> ? ? ? ?* reorg.c (label_before_next_insn): New function.
> ? ? ? ?(relax_delay_slots): Use it instead of prev_label.
> ? ? ? ?* rtl.h (prev_label): Delete declaration.
> ? ? ? ?* emit-rtl.c (prev_label): Remove.
>
> git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@180674 138bc75d-0d04-0410-961f-82ee72b054a4
> ---
> ?gcc/ChangeLog ?| ? ?7 +++++++
> ?gcc/emit-rtl.c | ? 15 ---------------
> ?gcc/reorg.c ? ?| ? 17 ++++++++++++++++-
> ?gcc/rtl.h ? ? ?| ? ?1 -
> ?4 files changed, 23 insertions(+), 17 deletions(-)
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 0eb34e5..e9bda2b 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,10 @@
> +2011-10-30 ?David S. Miller ?<davem@davemloft.net>
> +
> + ? ? ? * reorg.c (label_before_next_insn): New function.
> + ? ? ? (relax_delay_slots): Use it instead of prev_label.
> + ? ? ? * rtl.h (prev_label): Delete declaration.
> + ? ? ? * emit-rtl.c (prev_label): Remove.
> +
> ?2011-10-30 ?Revital Eres ?<revital.eres@linaro.org>
>
> ? ? ? ?* modulo-sched.c (generate_prolog_epilog): Mark prolog and epilog
> diff --git a/gcc/emit-rtl.c b/gcc/emit-rtl.c
> index 8465237..c2bc56b 100644
> --- a/gcc/emit-rtl.c
> +++ b/gcc/emit-rtl.c
> @@ -3330,21 +3330,6 @@ next_label (rtx insn)
> ? return insn;
> ?}
>
> -/* Return the last CODE_LABEL before the insn INSN, or 0 if there is none. ?*/
> -
> -rtx
> -prev_label (rtx insn)
> -{
> - ?while (insn)
> - ? ?{
> - ? ? ?insn = PREV_INSN (insn);
> - ? ? ?if (insn == 0 || LABEL_P (insn))
> - ? ? ? break;
> - ? ?}
> -
> - ?return insn;
> -}
> -
> ?/* Return the last label to mark the same position as LABEL. ?Return LABEL
> ? ?itself if it is null or any return rtx. ?*/
>
> diff --git a/gcc/reorg.c b/gcc/reorg.c
> index f77a3a0..40d73a7 100644
> --- a/gcc/reorg.c
> +++ b/gcc/reorg.c
> @@ -3349,6 +3349,21 @@ delete_jump (rtx insn)
> ? ? delete_computation (insn);
> ?}
>
> +static rtx
> +label_before_next_insn (rtx x, rtx scan_limit)
> +{
> + ?rtx insn = next_active_insn (x);
> + ?while (insn)
> + ? ?{
> + ? ? ?insn = PREV_INSN (insn);
> + ? ? ?if (insn == scan_limit || insn == NULL_RTX)
> + ? ? ? return NULL_RTX;
> + ? ? ?if (LABEL_P (insn))
> + ? ? ? break;
> + ? ?}
> + ?return insn;
> +}
> +
>
> ?/* Once we have tried two ways to fill a delay slot, make a pass over the
> ? ?code to try to improve the results and to do such things as more jump
> @@ -3634,7 +3649,7 @@ relax_delay_slots (rtx first)
> ? ? ? ? identical to the one in its delay slot. ?In this case, we can just
> ? ? ? ? delete the branch and the insn in its delay slot. ?*/
> ? ? ? if (next && NONJUMP_INSN_P (next)
> - ? ? ? ? && prev_label (next_active_insn (next)) == target_label
> + ? ? ? ? && label_before_next_insn (next, insn) == target_label
> ? ? ? ? ?&& simplejump_p (insn)
> ? ? ? ? ?&& XVECLEN (pat, 0) == 2
> ? ? ? ? ?&& rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
> diff --git a/gcc/rtl.h b/gcc/rtl.h
> index 81958a5..41536be 100644
> --- a/gcc/rtl.h
> +++ b/gcc/rtl.h
> @@ -1812,7 +1812,6 @@ extern rtx next_real_insn (rtx);
> ?extern rtx prev_active_insn (rtx);
> ?extern rtx next_active_insn (rtx);
> ?extern int active_insn_p (const_rtx);
> -extern rtx prev_label (rtx);
> ?extern rtx next_label (rtx);
> ?extern rtx skip_consecutive_labels (rtx);
> ?extern rtx next_cc0_user (rtx);
> --
> 1.7.6.401.g6a319
>
>