From patchwork Fri Oct 19 09:33:17 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 192624 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id AE1E62C008F for ; Fri, 19 Oct 2012 20:33:39 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1351244019; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Date: From:To:Subject:Message-ID:MIME-Version:Content-Type: Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=JwrrBCKpXvOhLEZZfPiKTO2ORRs=; b=mRn+tVu79j7r76F sYQMn9FnwY/5kMHjXbm49kOgmuCjl02t4BGSW2cQRKrFDQRfSUQuMCYKh1X5aAk7 YsiHnzqErstNeGyAoPKgU9N+GhTmri4YpjT7RQTl3Oxpqmq3B+Z4/Bp/nJy+Ojfb HTJOkeemjPoMtL6dYx/LUyCzJYlk= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Date:From:To:Subject:Message-ID:MIME-Version:Content-Type:Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=qv15CRVEidWKAshrCk7ggidgehBNnre4m65AMtfX6dQ6PtDvqhlzkHedcIG6lh Q+cH+Fa3PiP8azjVw5ScNFzHQC7BGzzmezO3p1FpFB5XCd6GamrKWXWGQdi/V6Xh qbInZcqKzNSPQnZqmFnL9zZFVKE8wOaw1EJ+e/1WI0jVA=; Received: (qmail 12346 invoked by alias); 19 Oct 2012 09:33:30 -0000 Received: (qmail 12338 invoked by uid 22791); 19 Oct 2012 09:33:29 -0000 X-SWARE-Spam-Status: No, hits=-4.0 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, RP_MATCHES_RCVD, TW_IV, TW_TM X-Spam-Check-By: sourceware.org Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 19 Oct 2012 09:33:23 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 0EBE7543869; Fri, 19 Oct 2012 11:33:17 +0200 (CEST) Date: Fri, 19 Oct 2012 11:33:17 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de Subject: Fix array bound niter estimate (PR middle-end/54937) Message-ID: <20121019093317.GA30010@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi, this patch fixes off-by-one error in the testcase attached. The problem is that dominance based test used by record_estimate to check whether the given statement must be executed at last iteration of the loop is wrong ignoring the side effect of other statements that may terminate the program. It also does not work for mulitple exits as excercised by cunroll-2.c testcase. This patch makes simple approach of computing set of all statements that must by executed last iteration first time record_estimate is executed this way. The set is computed conservatively walking header BB and its signle successors (possibly diving into nested loop) stopping on first BB with multiple exits. Better result can be computed by 1) estimating what loops are known to be finite 2) inserting fake edges for all infinite loop and all statements with side effect that may terminate the execution 3) using the post dominance info. But that seems too expensive for something that is executed several times per function compilation. In fact I am thinking about making recrod-estimate to happen at ivcanon time only and then making the loop_max_iterations and loop_estimated_iterations to simply return the bound instead of trying to recompute it all the time. Still I do not see us to care about very precise bound for loops having complex control flow since we do not really want to completely unroll them and elsewhere the off-by-one error in conservative direction for iteration estimate is not big deal. Bootstrapped/regtested x86_64-linux, seems sane? Honza PR middle-end/54937 * tree-ssa-loop-niter.c (compute_stmts_executed_last_iteration): New function. (record_estimate): Use it; remove confused dominance test. (estimate_numbers_of_iterations_loop): Free stmts_executed_last_iteration. * gcc.c-torture/execute/pr54937.c: Ne wtestcase. * testsuite/gcc.dg/tree-ssa/cunroll-2.c: Tighten. Index: tree-ssa-loop-niter.c =================================================================== *** tree-ssa-loop-niter.c (revision 192537) --- tree-ssa-loop-niter.c (working copy) *************** record_niter_bound (struct loop *loop, d *** 2523,2528 **** --- 2523,2580 ---- loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; } + /* Compute pointer set of statements in currently analyzed loop that are known + to be executed at last iteration and store it into AUX. + We do very simple job of recording statements in the superblock + starsting in loop header until reaching first statement with side effect. + + We can compute post-dominance after inserting fake edges to CFG + for all statements possibly terminating CFG and for all possibly + infinite subloops, but we really care about precise estimates + of simple loops with little control flow in it. */ + static void + compute_stmts_executed_last_iteration (struct loop *loop) + { + basic_block bb = loop->header; + pointer_set_t *visited = NULL; + gimple_stmt_iterator gsi; + pointer_set_t *stmts_executed_last_iteration; + + loop->aux = stmts_executed_last_iteration = pointer_set_create (); + while (true) + { + for (gsi = gsi_start_bb (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) + { + if (gimple_has_side_effects (gsi_stmt (gsi))) + { + if (visited) + pointer_set_destroy (visited); + return; + } + pointer_set_insert (stmts_executed_last_iteration, gsi_stmt (gsi)); + } + if (single_succ_p (bb)) + { + /* Deal with the rare case that there is an infintie loop inside the + loop examined. */ + if (!visited) + { + visited = pointer_set_create (); + pointer_set_insert (visited, bb); + } + bb = single_succ_edge (bb)->dest; + if (pointer_set_insert (visited, bb)) + break; + } + else + break; + } + if (visited) + pointer_set_destroy (visited); + return; + } + + /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT is true if the loop is exited immediately after STMT, and this exit is taken at last when the STMT is executed BOUND + 1 times. *************** record_estimate (struct loop *loop, tree *** 2535,2541 **** gimple at_stmt, bool is_exit, bool realistic, bool upper) { double_int delta; - edge exit; if (dump_file && (dump_flags & TDF_DETAILS)) { --- 2587,2592 ---- *************** record_estimate (struct loop *loop, tree *** 2573,2586 **** If at_stmt is an exit or dominates the single exit from the loop, then the loop latch is executed at most BOUND times, otherwise it can be executed BOUND + 1 times. */ ! exit = single_exit (loop); ! if (is_exit ! || (exit != NULL ! && dominated_by_p (CDI_DOMINATORS, ! exit->src, gimple_bb (at_stmt)))) delta = double_int_zero; else ! delta = double_int_one; i_bound += delta; /* If an overflow occurred, ignore the result. */ --- 2624,2641 ---- If at_stmt is an exit or dominates the single exit from the loop, then the loop latch is executed at most BOUND times, otherwise it can be executed BOUND + 1 times. */ ! if (is_exit) delta = double_int_zero; else ! { ! if (!loop->aux) ! compute_stmts_executed_last_iteration (loop); ! if (pointer_set_contains ((pointer_set_t *)loop->aux, ! at_stmt)) ! delta = double_int_zero; ! else ! delta = double_int_one; ! } i_bound += delta; /* If an overflow occurred, ignore the result. */ *************** estimate_numbers_of_iterations_loop (str *** 2971,2976 **** --- 3026,3033 ---- if (loop->estimate_state != EST_NOT_COMPUTED) return; + gcc_assert (!loop->aux); + loop->estimate_state = EST_AVAILABLE; /* Force estimate compuation but leave any existing upper bound in place. */ loop->any_estimate = false; *************** estimate_numbers_of_iterations_loop (str *** 3004,3009 **** --- 3061,3071 ---- bound = gcov_type_to_double_int (nit); record_niter_bound (loop, bound, true, false); } + if (loop->aux) + { + pointer_set_destroy ((pointer_set_t *)loop->aux); + loop->aux = NULL; + } } /* Sets NIT to the estimated number of executions of the latch of the Index: testsuite/gcc.c-torture/execute/pr54937.c =================================================================== --- testsuite/gcc.c-torture/execute/pr54937.c (revision 0) +++ testsuite/gcc.c-torture/execute/pr54937.c (revision 0) @@ -0,0 +1,22 @@ + +void exit (int); +void abort (void); +int a[1]; +void (*terminate_me)(int); + +__attribute__((noinline,noclone)) +t(int c) +{ int i; + for (i=0;i