From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 73206 invoked by alias); 1 Oct 2015 11:39:57 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 73184 invoked by uid 89); 1 Oct 2015 11:39:55 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.0 required=5.0 tests=AWL,BAYES_00,SPF_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Thu, 01 Oct 2015 11:39:50 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id EC61CAC6C; Thu, 1 Oct 2015 11:39:45 +0000 (UTC) Date: Thu, 01 Oct 2015 11:39:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jan Hubicka Subject: [PATCH] Fix PR67783, quadraticness in IPA inline analysis Message-ID: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2015-10/txt/msg00038.txt.bz2 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?) Thanks, Richard. 2015-10-01 Richard Biener 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 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 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);