On Tue, Nov 20, 2018 at 2:23 PM Michael Matz <[email protected]> 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)
