Fix PR37916 (compile time regression)

Fix PR37916 (compile time regression)

[Michael Matz]

Hi,

the testcase gcc.dg/20020425-1.c was once a compile time hog.  With 
current trunk it only needs 7 seconds (on my machine, with -O0 cc1) but 
there's still something to improve as virtually all of that time is 
wasted in repeatedly scanning the same (long) sequence of gimple 
statements to possibly give them locations.  Basically it's:

  gimplify_stmt (E)
    gimplify_expr (E)
      gimplify_cond_expr (E)
        gimplify_stmt (E.then)
          gimplify_expr (E.then)
            update_locs (seq1)
        gimplify_stmt (E.else)
          gimplify_expr (E.else)
            update_locs (seq2);
        return (seq = seq1 + seq2)
      update_locs (seq)

So the tails of the sequence (containing the expanded then/else subtrees) 
are repeatedly iterated over to give them locations from E, even if they 
already have locations from E.then and E.else.  That's quadratic.

So let's avoid this, as the patch does.  If we are sure that the 
subsequence has locations (namely when E.then or E.else have locations) 
return that sequence not in *pre_p but in something else that isn't 
iterated over but appended to *pre_p in the caller.

That shoves off most time and it now takes 0.25 seconds.

The bug report contains some discussion about how the recursion between 
gimplify_expr->gimplify_cond_expr is bad, and I'm not tackling that.  It 
would only be possible with an explicit stack (as these trees _are_ 
recursive) and the testcase is not as deeply nested to need that on normal 
stack sizes.

But it's not a time hog anymore, so should we marked it fixed 
nevertheless?

Anyway, regstrapped on x86-64-linux, no regressions.  Okay for trunk?


Ciao,
Michael.

	PR middle-end/38059
	* gimplify.c (gimplify_cond_expr): Add MIDDLE argument, use
	for passing back part of generated sequence.
	(gimplify_expr): Change call to gimplify_cond_expr, don't
	iterate through middle for updating locations.

diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index 87082ad10d2a..719f4ba379ed 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -3940,10 +3940,14 @@ generic_expr_could_trap_p (tree expr)
     The second form is used when *EXPR_P is of type void.
 
     PRE_P points to the list where side effects that must happen before
-      *EXPR_P should be stored.  */
+      *EXPR_P should be stored.
+    MIDDLE points to a sequence that possibly contains the lowered
+      statements for the two arms; must be appended to *PRE_P in the
+      caller.  */
 
 static enum gimplify_status
-gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
+gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *middle,
+		    fallback_t fallback)
 {
   tree expr = *expr_p;
   tree type = TREE_TYPE (expr);
@@ -3952,10 +3956,17 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
   enum gimplify_status ret;
   tree label_true, label_false, label_cont;
   bool have_then_clause_p, have_else_clause_p;
+  location_t loc1, loc2;
   gcond *cond_stmt;
   enum tree_code pred_code;
   gimple_seq seq = NULL;
 
+  loc1 = TREE_OPERAND (expr, 1)
+	   ? EXPR_LOCATION (TREE_OPERAND (expr, 1))
+	   : UNKNOWN_LOCATION;
+  loc2 = TREE_OPERAND (expr, 2)
+	   ? EXPR_LOCATION (TREE_OPERAND (expr, 2))
+	   : UNKNOWN_LOCATION;
   /* If this COND_EXPR has a value, copy the values into a temporary within
      the arms.  */
   if (!VOID_TYPE_P (type))
@@ -4098,6 +4109,7 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
 				 &arm2);
   cond_stmt = gimple_build_cond (pred_code, arm1, arm2, label_true,
 				 label_false);
+  gimple_set_location (cond_stmt, input_location);
   gimple_set_no_warning (cond_stmt, TREE_NO_WARNING (COND_EXPR_COND (expr)));
   gimplify_seq_add_stmt (&seq, cond_stmt);
   gimple_stmt_iterator gsi = gsi_last (seq);
@@ -4150,7 +4162,15 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
     gimplify_seq_add_stmt (&seq, gimple_build_label (label_cont));
 
   gimple_pop_condition (pre_p);
-  gimple_seq_add_seq (pre_p, seq);
+
+  /* If SEQ contains only statements that certainly will have a location
+     there's no need for our caller to retry setting another location,
+     so put that sequence into *MIDDLE.  Otherwise just append to *PRE_P.  */
+  if ((!have_then_clause_p || loc1 != UNKNOWN_LOCATION)
+      && (!have_else_clause_p || loc2 != UNKNOWN_LOCATION))
+    gimple_seq_add_seq (middle, seq);
+  else
+    gimple_seq_add_seq (pre_p, seq);
 
   if (ret == GS_ERROR)
     ; /* Do nothing.  */
@@ -12182,6 +12202,7 @@ gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p,
   tree tmp;
   gimple_seq internal_pre = NULL;
   gimple_seq internal_post = NULL;
+  gimple_seq middle = NULL;
   tree save_expr;
   bool is_statement;
   location_t saved_location;
@@ -12319,7 +12340,7 @@ gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p,
 	  break;
 
 	case COND_EXPR:
-	  ret = gimplify_cond_expr (expr_p, pre_p, fallback);
+	  ret = gimplify_cond_expr (expr_p, pre_p, &middle, fallback);
 
 	  /* C99 code may assign to an array in a structure value of a
 	     conditional expression, and this has undefined behavior
@@ -13236,7 +13257,9 @@ gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p,
       /* The result of gimplifying *EXPR_P is going to be the last few
 	 statements in *PRE_P and *POST_P.  Add location information
 	 to all the statements that were added by the gimplification
-	 helpers.  */
+	 helpers.  The sequence MIDDLE belongs between *PRE_P and *POST_P
+	 but is certain to have location set, so avoid the quadraticness
+	 of repeatedly setting locations.  */
       if (!gimple_seq_empty_p (*pre_p))
 	annotate_all_with_location_after (*pre_p, pre_last_gsi, input_location);
 
@@ -13244,8 +13267,10 @@ gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p,
 	annotate_all_with_location_after (*post_p, post_last_gsi,
 					  input_location);
 
+      gimple_seq_add_seq (pre_p, middle);
       goto out;
     }
+  gimple_seq_add_seq (pre_p, middle);
 
 #ifdef ENABLE_GIMPLE_CHECKING
   if (*expr_p)

Re: Fix PR37916 (compile time regression)

[Richard Biener]

On Tue, Nov 20, 2018 at 2:23 PM Michael Matz <matz@suse.de> wrote:
>
> Hi,
>
> the testcase gcc.dg/20020425-1.c was once a compile time hog.  With
> current trunk it only needs 7 seconds (on my machine, with -O0 cc1) but
> there's still something to improve as virtually all of that time is
> wasted in repeatedly scanning the same (long) sequence of gimple
> statements to possibly give them locations.  Basically it's:
>
>   gimplify_stmt (E)
>     gimplify_expr (E)
>       gimplify_cond_expr (E)
>         gimplify_stmt (E.then)
>           gimplify_expr (E.then)
>             update_locs (seq1)
>         gimplify_stmt (E.else)
>           gimplify_expr (E.else)
>             update_locs (seq2);
>         return (seq = seq1 + seq2)
>       update_locs (seq)
>
> So the tails of the sequence (containing the expanded then/else subtrees)
> are repeatedly iterated over to give them locations from E, even if they
> already have locations from E.then and E.else.  That's quadratic.
>
> So let's avoid this, as the patch does.  If we are sure that the
> subsequence has locations (namely when E.then or E.else have locations)
> return that sequence not in *pre_p but in something else that isn't
> iterated over but appended to *pre_p in the caller.
>
> That shoves off most time and it now takes 0.25 seconds.
>
> The bug report contains some discussion about how the recursion between
> gimplify_expr->gimplify_cond_expr is bad, and I'm not tackling that.  It
> would only be possible with an explicit stack (as these trees _are_
> recursive) and the testcase is not as deeply nested to need that on normal
> stack sizes.
>
> But it's not a time hog anymore, so should we marked it fixed
> nevertheless?
>
> Anyway, regstrapped on x86-64-linux, no regressions.  Okay for trunk?

Ick.  Given you do that only for one stmt kind and it looks kind of ugly
wouldn't it be better to splat out gimple_set_location (g, input_location)
to all 108 places that call gimple_build_* in gimplify.c and get rid of
that ugly location post-processing?  I also wonder why we do not simply
rely on the "surrounding" location handing of UNKNOWN_LOCATION and,
say, simply only annotate the "main" gimplified stmt with the expr location?

Richard.

>
> Ciao,
> Michael.
>
>         PR middle-end/38059
>         * gimplify.c (gimplify_cond_expr): Add MIDDLE argument, use
>         for passing back part of generated sequence.
>         (gimplify_expr): Change call to gimplify_cond_expr, don't
>         iterate through middle for updating locations.
>
> diff --git a/gcc/gimplify.c b/gcc/gimplify.c
> index 87082ad10d2a..719f4ba379ed 100644
> --- a/gcc/gimplify.c
> +++ b/gcc/gimplify.c
> @@ -3940,10 +3940,14 @@ generic_expr_could_trap_p (tree expr)
>      The second form is used when *EXPR_P is of type void.
>
>      PRE_P points to the list where side effects that must happen before
> -      *EXPR_P should be stored.  */
> +      *EXPR_P should be stored.
> +    MIDDLE points to a sequence that possibly contains the lowered
> +      statements for the two arms; must be appended to *PRE_P in the
> +      caller.  */
>
>  static enum gimplify_status
> -gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
> +gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *middle,
> +                   fallback_t fallback)
>  {
>    tree expr = *expr_p;
>    tree type = TREE_TYPE (expr);
> @@ -3952,10 +3956,17 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
>    enum gimplify_status ret;
>    tree label_true, label_false, label_cont;
>    bool have_then_clause_p, have_else_clause_p;
> +  location_t loc1, loc2;
>    gcond *cond_stmt;
>    enum tree_code pred_code;
>    gimple_seq seq = NULL;
>
> +  loc1 = TREE_OPERAND (expr, 1)
> +          ? EXPR_LOCATION (TREE_OPERAND (expr, 1))
> +          : UNKNOWN_LOCATION;
> +  loc2 = TREE_OPERAND (expr, 2)
> +          ? EXPR_LOCATION (TREE_OPERAND (expr, 2))
> +          : UNKNOWN_LOCATION;
>    /* If this COND_EXPR has a value, copy the values into a temporary within
>       the arms.  */
>    if (!VOID_TYPE_P (type))
> @@ -4098,6 +4109,7 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
>                                  &arm2);
>    cond_stmt = gimple_build_cond (pred_code, arm1, arm2, label_true,
>                                  label_false);
> +  gimple_set_location (cond_stmt, input_location);
>    gimple_set_no_warning (cond_stmt, TREE_NO_WARNING (COND_EXPR_COND (expr)));
>    gimplify_seq_add_stmt (&seq, cond_stmt);
>    gimple_stmt_iterator gsi = gsi_last (seq);
> @@ -4150,7 +4162,15 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
>      gimplify_seq_add_stmt (&seq, gimple_build_label (label_cont));
>
>    gimple_pop_condition (pre_p);
> -  gimple_seq_add_seq (pre_p, seq);
> +
> +  /* If SEQ contains only statements that certainly will have a location
> +     there's no need for our caller to retry setting another location,
> +     so put that sequence into *MIDDLE.  Otherwise just append to *PRE_P.  */
> +  if ((!have_then_clause_p || loc1 != UNKNOWN_LOCATION)
> +      && (!have_else_clause_p || loc2 != UNKNOWN_LOCATION))
> +    gimple_seq_add_seq (middle, seq);
> +  else
> +    gimple_seq_add_seq (pre_p, seq);
>
>    if (ret == GS_ERROR)
>      ; /* Do nothing.  */
> @@ -12182,6 +12202,7 @@ gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p,
>    tree tmp;
>    gimple_seq internal_pre = NULL;
>    gimple_seq internal_post = NULL;
> +  gimple_seq middle = NULL;
>    tree save_expr;
>    bool is_statement;
>    location_t saved_location;
> @@ -12319,7 +12340,7 @@ gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p,
>           break;
>
>         case COND_EXPR:
> -         ret = gimplify_cond_expr (expr_p, pre_p, fallback);
> +         ret = gimplify_cond_expr (expr_p, pre_p, &middle, fallback);
>
>           /* C99 code may assign to an array in a structure value of a
>              conditional expression, and this has undefined behavior
> @@ -13236,7 +13257,9 @@ gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p,
>        /* The result of gimplifying *EXPR_P is going to be the last few
>          statements in *PRE_P and *POST_P.  Add location information
>          to all the statements that were added by the gimplification
> -        helpers.  */
> +        helpers.  The sequence MIDDLE belongs between *PRE_P and *POST_P
> +        but is certain to have location set, so avoid the quadraticness
> +        of repeatedly setting locations.  */
>        if (!gimple_seq_empty_p (*pre_p))
>         annotate_all_with_location_after (*pre_p, pre_last_gsi, input_location);
>
> @@ -13244,8 +13267,10 @@ gimplify_expr (tree *expr_p, gimple_seq *pre_p, gimple_seq *post_p,
>         annotate_all_with_location_after (*post_p, post_last_gsi,
>                                           input_location);
>
> +      gimple_seq_add_seq (pre_p, middle);
>        goto out;
>      }
> +  gimple_seq_add_seq (pre_p, middle);
>
>  #ifdef ENABLE_GIMPLE_CHECKING
>    if (*expr_p)

Re: Fix PR37916 (compile time regression)

[Michael Matz]

Hi,

On Tue, 20 Nov 2018, Richard Biener wrote:

> > Anyway, regstrapped on x86-64-linux, no regressions.  Okay for trunk?
> 
> Ick.  Given you do that only for one stmt kind and it looks kind of ugly 
> wouldn't it be better to splat out gimple_set_location (g, 
> input_location) to all 108 places that call gimple_build_* in gimplify.c 
> and get rid of that ugly location post-processing?

I thought about this and rejected it for stage 3, but if you say that's 
feasible I'll work on that; it is indeed nicer.

> I also wonder why we do not simply rely on the "surrounding" location 
> handing of UNKNOWN_LOCATION and, say, simply only annotate the "main" 
> gimplified stmt with the expr location?

Yeah.  Though that will be harder to verify to be correct (or at least not 
regressing vis the current state).


Ciao,
Michael.

Re: Fix PR37916 (compile time regression)

[Richard Biener]

On Tue, Nov 20, 2018 at 3:19 PM Michael Matz <matz@suse.de> wrote:
>
> Hi,
>
> On Tue, 20 Nov 2018, Richard Biener wrote:
>
> > > Anyway, regstrapped on x86-64-linux, no regressions.  Okay for trunk?
> >
> > Ick.  Given you do that only for one stmt kind and it looks kind of ugly
> > wouldn't it be better to splat out gimple_set_location (g,
> > input_location) to all 108 places that call gimple_build_* in gimplify.c
> > and get rid of that ugly location post-processing?
>
> I thought about this and rejected it for stage 3, but if you say that's
> feasible I'll work on that; it is indeed nicer.

If you can try that would be nice, and yes, given it fixes a bug it's
OK for stage3.

> > I also wonder why we do not simply rely on the "surrounding" location
> > handing of UNKNOWN_LOCATION and, say, simply only annotate the "main"
> > gimplified stmt with the expr location?
>
> Yeah.  Though that will be harder to verify to be correct (or at least not
> regressing vis the current state).

True.  Nevertheless eventually good enough ;)

Richard.

>
> Ciao,
> Michael.