From 73fb742dc21731162383dffb76f98e70d75af450 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Mon, 12 Oct 2015 12:26:02 +0000 Subject: [PATCH] re PR ipa/67783 (quadratic time consumption in IPA inlining with -O1 and higher) 2015-10-12 Richard Biener PR ipa/67783 * ipa-inline-analysis.c (estimate_function_body_sizes): Re-add code that analyzes IVs on each stmt but in a cheaper way avoiding quadratic behavior. From-SVN: r228710 --- gcc/ChangeLog | 7 ++++ gcc/ipa-inline-analysis.c | 73 +++++++++++++++++++++++++-------------- 2 files changed, 55 insertions(+), 25 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7a70e589932..9f4e5ab32be 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2015-10-12 Richard Biener + + PR ipa/67783 + * ipa-inline-analysis.c (estimate_function_body_sizes): Re-add + code that analyzes IVs on each stmt but in a cheaper way avoiding + quadratic behavior. + 2015-10-12 Nick Clifton * config/msp430/msp430.c (msp430_mcu_names): Rename to diff --git a/gcc/ipa-inline-analysis.c b/gcc/ipa-inline-analysis.c index 786ba438a8c..38e1ec0d5c5 100644 --- a/gcc/ipa-inline-analysis.c +++ b/gcc/ipa-inline-analysis.c @@ -2786,37 +2786,60 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early) &will_be_nonconstant); } exits.release (); + } - for (gphi_iterator gsi = gsi_start_phis (loop->header); - !gsi_end_p (gsi); gsi_next (&gsi)) + /* To avoid quadratic behavior we analyze stride predicates only + with respect to the containing loop. Thus we simply iterate + over all defs in the outermost loop body. */ + for (loop = loops_for_fn (cfun)->tree_root->inner; + loop != NULL; loop = loop->next) + { + basic_block *body = get_loop_body (loop); + for (unsigned i = 0; i < loop->num_nodes; i++) { - gphi *phi = gsi.phi (); - tree use = gimple_phi_result (phi); - affine_iv iv; - predicate will_be_nonconstant; - if (virtual_operand_p (use) - || !simple_iv (loop, loop, use, &iv, true) - || is_gimple_min_invariant (iv.step)) - continue; - will_be_nonconstant - = will_be_nonconstant_expr_predicate (fbi.info, info, - iv.step, - nonconstant_names); - if (!true_predicate_p (&will_be_nonconstant)) - will_be_nonconstant = and_predicates (info->conds, - &bb_predicate, - &will_be_nonconstant); - if (!true_predicate_p (&will_be_nonconstant) - && !false_predicate_p (&will_be_nonconstant)) - /* This is slightly inprecise. We may want to represent - each loop with independent predicate. */ - loop_stride = and_predicates (info->conds, &loop_stride, - &will_be_nonconstant); + gimple_stmt_iterator gsi; + bb_predicate = *(struct predicate *) body[i]->aux; + for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); + gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + + if (!is_gimple_assign (stmt)) + continue; + + tree def = gimple_assign_lhs (stmt); + if (TREE_CODE (def) != SSA_NAME) + continue; + + affine_iv iv; + if (!simple_iv (loop_containing_stmt (stmt), + loop_containing_stmt (stmt), + def, &iv, true) + || is_gimple_min_invariant (iv.step)) + continue; + + predicate will_be_nonconstant + = will_be_nonconstant_expr_predicate (fbi.info, info, + iv.step, + nonconstant_names); + if (!true_predicate_p (&will_be_nonconstant)) + will_be_nonconstant + = and_predicates (info->conds, &bb_predicate, + &will_be_nonconstant); + if (!true_predicate_p (&will_be_nonconstant) + && !false_predicate_p (&will_be_nonconstant)) + /* This is slightly inprecise. We may want to represent + each loop with independent predicate. */ + loop_stride = and_predicates (info->conds, &loop_stride, + &will_be_nonconstant); + } } + free (body); } set_hint_predicate (&inline_summaries->get (node)->loop_iterations, loop_iterations); - set_hint_predicate (&inline_summaries->get (node)->loop_stride, loop_stride); + set_hint_predicate (&inline_summaries->get (node)->loop_stride, + loop_stride); scev_finalize (); } FOR_ALL_BB_FN (bb, my_function) -- 2.30.2