This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix PR67783, quadraticness in IPA inline analysis
- From: Richard Biener <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Jan Hubicka <hubicka at ucw dot cz>
- Date: Mon, 5 Oct 2015 13:15:30 +0200 (CEST)
- Subject: Re: [PATCH] Fix PR67783, quadraticness in IPA inline analysis
- Authentication-results: sourceware.org; auth=none
- References: <alpine dot LSU dot 2 dot 11 dot 1510011333230 dot 6516 at zhemvz dot fhfr dot qr>
On Thu, 1 Oct 2015, Richard Biener wrote:
>
> The following avoids quadraticness in the loop depth by only considering
> loop header defs as IVs for the analysis of the loop_stride predicate.
> This will miss cases like
>
> foo (int inv)
> {
> for (i = inv; i < n; ++i)
> {
> int derived_iv = i + i * inv;
> ...
> }
> }
>
> but I doubt that's important in practice. Another way would be to
> just consider the containing loop when analyzing the IV, thus iterate
> over outermost loop bodies only, replacing the
>
> simple_iv (loop, loop_containing_stmt (stmt), use, &iv, true)
>
> check with
>
> simple_iv (loop_containing_stmt (stmt), loop_containing_stmt (stmt),
> use, &iv, true);
>
> but doing all this analysis for each stmt is already quite expensive,
> esp. as we are doing it for all uses instead of all defs ...
>
> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
>
> Honza, is this ok or did you do the current way on purpose (rather
> than for completeness as it was easy to do?)
Applied as r228472.
Richard.
> Thanks,
> Richard.
>
> 2015-10-01 Richard Biener <rguenther@suse.de>
>
> PR ipa/67783
> * ipa-inline-analysis.c (estimate_function_body_sizes): Only
> consider loop header PHI defs as IVs.
>
> Index: gcc/ipa-inline-analysis.c
> ===================================================================
> *** gcc/ipa-inline-analysis.c (revision 228319)
> --- gcc/ipa-inline-analysis.c (working copy)
> *************** estimate_function_body_sizes (struct cgr
> *** 2760,2768 ****
> {
> vec<edge> exits;
> edge ex;
> ! unsigned int j, i;
> struct tree_niter_desc niter_desc;
> - basic_block *body = get_loop_body (loop);
> bb_predicate = *(struct predicate *) loop->header->aux;
>
> exits = get_loop_exit_edges (loop);
> --- 2760,2767 ----
> {
> vec<edge> exits;
> edge ex;
> ! unsigned int j;
> struct tree_niter_desc niter_desc;
> bb_predicate = *(struct predicate *) loop->header->aux;
>
> exits = get_loop_exit_edges (loop);
> *************** estimate_function_body_sizes (struct cgr
> *** 2788,2833 ****
> }
> exits.release ();
>
> ! for (i = 0; i < loop->num_nodes; i++)
> {
> ! 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);
> ! affine_iv iv;
> ! ssa_op_iter iter;
> ! tree use;
> !
> ! FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
> ! {
> ! predicate will_be_nonconstant;
> !
> ! if (!simple_iv
> ! (loop, loop_containing_stmt (stmt), 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);
> ! }
> ! }
> }
> - free (body);
> }
> set_hint_predicate (&inline_summaries->get (node)->loop_iterations,
> loop_iterations);
> --- 2787,2818 ----
> }
> exits.release ();
>
> ! for (gphi_iterator gsi = gsi_start_phis (loop->header);
> ! !gsi_end_p (gsi); gsi_next (&gsi))
> {
> ! 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);
> }
> }
> set_hint_predicate (&inline_summaries->get (node)->loop_iterations,
> loop_iterations);
>
--
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)