On Tue, Nov 20, 2018 at 2:23 PM Michael Matz <m...@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)