From patchwork Wed Oct 31 10:39:49 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 195829 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 2E3612C009F for ; Wed, 31 Oct 2012 21:40:09 +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=1352284810; 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=OR3jsoaP0bBivGGgbkRq81LvmDs=; b=DRG6KTiwhdOmjr1 RzE0XRW7FvGJNsD55oA3Fdq6+tmKBafcSNq3ZAC5fGTQMAqCGQRdHu4HNcdQTaIm wtx7WUweia2A21gHZjO/58z3dwF9cJKMRhOWn2LVkNzdJ+Y2VC0teTKNRaUGVXJ1 uYNZpavBq6VQ5ix6T4ViX/0yIrTk= 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=ucHAWADa09XifLyPvejz+fyzjkTtQFQeEdhF5MBFVVvqxKM962fngeCNS5Lt5w 7xsLkUSjBDxWbCTC9isTorqzIkbh06GLjZUkEq9KVqfa005zIOUnCacvPNnxZWZj 7SDK1CNdkugjKLKux+7FS3EiqTuvOZ8R9x0sp4hu6YTGo=; Received: (qmail 4990 invoked by alias); 31 Oct 2012 10:40:01 -0000 Received: (qmail 4842 invoked by uid 22791); 31 Oct 2012 10:40:00 -0000 X-SWARE-Spam-Status: No, hits=-4.1 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_CF, 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; Wed, 31 Oct 2012 10:39:51 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 6D360543B8C; Wed, 31 Oct 2012 11:39:49 +0100 (CET) Date: Wed, 31 Oct 2012 11:39:49 +0100 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de Subject: Non-dominating loop bounds in tree-ssa-loop-niter 3/4 Message-ID: <20121031103949.GD19020@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 implements the logic to remove statements that are known to be undefined and thus expected to not be executed after unrolling. It also removes redundant exits that I originally tried to do at once, but it does not fly, since the peeling confuse number_of_iterations_exit and it no longer understands the ivs. So now we 1) always remove exits that are known to be redundant by the bounds found 2) try to peel/unroll 3) if success remove statemnts from the last iteration This silence the array-bounds warnings in my testcase and many cases of -O3 bootstrap (I am running it now). Still if one construct testcase touching out of bound in more than one iteration we will produce false warning, I will do that incrementally by similar logic in loop copying. Bootstrapped/regtested x86_64-linux, OK? Honza * tree-ssa-loop-niter.c (free_loop_bounds): Break out from ... (free_numbers_of_iterations_estimates_loop): ... here. * tree-ssa-loop-ivcanon.c (remove_exits_and_undefined_stmts): New function. (remove_redundant_iv_test): New function. (try_unroll_loop_completely): Pass in MAXITER; use remove_exits_and_undefined_stmts (canonicalize_loop_induction_variables): Compute MAXITER; use remove_redundant_iv_test. * cfgloop.h (free_loop_bounds): New function. * gcc.dg/tree-ssa/cunroll-10.c: New testcase. * gcc.dg/tree-ssa/cunroll-9.c: New testcase. Index: tree-ssa-loop-niter.c =================================================================== --- tree-ssa-loop-niter.c (revision 192989) @@ -3505,15 +3737,11 @@ scev_probably_wraps_p (tree base, tree s return true; } -/* Frees the information on upper bounds on numbers of iterations of LOOP. */ - void -free_numbers_of_iterations_estimates_loop (struct loop *loop) +free_loop_bounds (struct loop *loop) { struct nb_iter_bound *bound, *next; - loop->nb_iterations = NULL; - loop->estimate_state = EST_NOT_COMPUTED; for (bound = loop->bounds; bound; bound = next) { next = bound->next; @@ -3523,6 +3751,16 @@ free_numbers_of_iterations_estimates_loo loop->bounds = NULL; } +/* Frees the information on upper bounds on numbers of iterations of LOOP. */ + +void +free_numbers_of_iterations_estimates_loop (struct loop *loop) +{ + loop->nb_iterations = NULL; + loop->estimate_state = EST_NOT_COMPUTED; + free_loop_bounds (loop); +} + /* Frees the information on upper bounds on numbers of iterations of loops. */ void Index: tree-ssa-loop-ivcanon.c =================================================================== --- tree-ssa-loop-ivcanon.c (revision 192989) +++ tree-ssa-loop-ivcanon.c (working copy) @@ -389,6 +389,116 @@ loop_edge_to_cancel (struct loop *loop) return NULL; } +/* Remove all tests for exits that are known to be taken after LOOP was + peeled NPEELED times. Put gcc_unreachable before every statement + known to not be executed. */ + +static bool +remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled) +{ + struct nb_iter_bound *elt; + bool changed = false; + + for (elt = loop->bounds; elt; elt = elt->next) + { + /* If statement is known to be undefined after peeling, turn it + into unreachable (or trap when debugging experience is supposed + to be good). */ + if (!elt->is_exit + && elt->bound.ule (double_int::from_uhwi (npeeled))) + { + gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt); + gimple stmt = gimple_build_call + (builtin_decl_implicit (optimize_debug + ? BUILT_IN_TRAP : BUILT_IN_UNREACHABLE), + 0); + + gimple_set_location (stmt, gimple_location (elt->stmt)); + gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); + changed = true; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Forced statement unreachable: "); + print_gimple_stmt (dump_file, elt->stmt, 0, 0); + } + } + /* If we know the exit will be taken after peeling, update. */ + else if (elt->is_exit + && elt->bound.ule (double_int::from_uhwi (npeeled))) + { + basic_block bb = gimple_bb (elt->stmt); + edge exit_edge = EDGE_SUCC (bb, 0); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Forced exit to be taken: "); + print_gimple_stmt (dump_file, elt->stmt, 0, 0); + } + if (!loop_exit_edge_p (loop, exit_edge)) + exit_edge = EDGE_SUCC (bb, 1); + if (exit_edge->flags & EDGE_TRUE_VALUE) + gimple_cond_make_true (elt->stmt); + else + gimple_cond_make_false (elt->stmt); + update_stmt (elt->stmt); + changed = true; + } + } + return changed; +} + +/* Remove all exits that are known to be never taken because of the loop bound + discovered. */ + +static bool +remove_redundant_iv_test (struct loop *loop) +{ + struct nb_iter_bound *elt; + bool changed = false; + + if (!loop->any_upper_bound) + return false; + for (elt = loop->bounds; elt; elt = elt->next) + { + /* Exit is pointless if it won't be taken before loop reaches + upper bound. */ + if (elt->is_exit && loop->any_upper_bound + && loop->nb_iterations_upper_bound.ult (elt->bound)) + { + basic_block bb = gimple_bb (elt->stmt); + edge exit_edge = EDGE_SUCC (bb, 0); + struct tree_niter_desc niter; + + if (!loop_exit_edge_p (loop, exit_edge)) + exit_edge = EDGE_SUCC (bb, 1); + + /* Only when we know the actual number of iterations, not + just a bound, we can remove the exit. */ + if (!number_of_iterations_exit (loop, exit_edge, + &niter, false, false)) + gcc_unreachable (); + if (!integer_onep (niter.assumptions) + || !integer_zerop (niter.may_be_zero) + || !niter.niter + || TREE_CODE (niter.niter) != INTEGER_CST) + continue; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Removed pointless exit: "); + print_gimple_stmt (dump_file, elt->stmt, 0, 0); + } + if (exit_edge->flags & EDGE_TRUE_VALUE) + gimple_cond_make_false (elt->stmt); + else + gimple_cond_make_true (elt->stmt); + update_stmt (elt->stmt); + changed = true; + } + } + return changed; +} + /* Tries to unroll LOOP completely, i.e. NITER times. UL determines which loops we are allowed to unroll. EXIT is the exit of the loop that should be eliminated. @@ -396,20 +511,22 @@ loop_edge_to_cancel (struct loop *loop) irreducible regions may become invalid as a result of the transformation. LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case - when we need to go into loop closed SSA form. */ + when we need to go into loop closed SSA form. + MAXITER specfy bound on number of iterations, -1 if it is + not known or too large for HOST_WIDE_INT. */ static bool try_unroll_loop_completely (struct loop *loop, edge exit, tree niter, enum unroll_level ul, bool *irred_invalidated, - bitmap loop_closed_ssa_invalidated) + bitmap loop_closed_ssa_invalidated, + HOST_WIDE_INT maxiter) { unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; gimple cond; struct loop_size size; bool n_unroll_found = false; - HOST_WIDE_INT maxiter; basic_block latch; edge latch_edge; location_t locus; @@ -445,7 +562,6 @@ try_unroll_loop_completely (struct loop exit = NULL; /* See if we can improve our estimate by using recorded loop bounds. */ - maxiter = max_loop_iterations_int (loop); if (maxiter >= 0 && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll)) { @@ -545,6 +661,8 @@ try_unroll_loop_completely (struct loop free_original_copy_tables (); } + remove_exits_and_undefined_stmts (loop, n_unroll); + /* Remove the conditional from the last copy of the loop. */ if (edge_to_cancel) { @@ -627,6 +745,8 @@ canonicalize_loop_induction_variables (s { edge exit = NULL; tree niter; + HOST_WIDE_INT maxiter; + bool modified = false; niter = number_of_latch_executions (loop); if (TREE_CODE (niter) == INTEGER_CST) @@ -657,6 +777,8 @@ canonicalize_loop_induction_variables (s if (niter && TREE_CODE (niter) == INTEGER_CST) record_niter_bound (loop, tree_to_double_int (niter), false, true); + maxiter = max_loop_iterations_int (loop); + if (dump_file && (dump_flags & TDF_DETAILS) && TREE_CODE (niter) == INTEGER_CST) { @@ -665,21 +787,28 @@ canonicalize_loop_induction_variables (s fprintf (dump_file, " times.\n"); } if (dump_file && (dump_flags & TDF_DETAILS) - && max_loop_iterations_int (loop) >= 0) + && maxiter >= 0) { fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num, - (int)max_loop_iterations_int (loop)); + (int)maxiter); } + /* Remove exits that are known to be never taken based on loop bound. + Needs to be called after compilation of max_loop_iterations_int that + populates the loop bounds. */ + modified |= remove_redundant_iv_test (loop); + if (try_unroll_loop_completely (loop, exit, niter, ul, irred_invalidated, - loop_closed_ssa_invalidated)) + loop_closed_ssa_invalidated, maxiter)) return true; if (create_iv && niter && !chrec_contains_undetermined (niter)) create_canonical_iv (loop, exit, niter); - return false; + if (modified) + free_loop_bounds (loop); + return modified; } /* The main entry point of the pass. Adds canonical induction variables Index: cfgloop.h =================================================================== --- cfgloop.h (revision 192989) +++ cfgloop.h (working copy) @@ -286,6 +286,7 @@ extern unsigned expected_loop_iterations extern rtx doloop_condition_get (rtx); void estimate_numbers_of_iterations_loop (struct loop *); +void free_loop_bounds (struct loop *); void record_niter_bound (struct loop *, double_int, bool, bool); bool estimated_loop_iterations (struct loop *, double_int *); bool max_loop_iterations (struct loop *, double_int *); Index: testsuite/gcc.dg/tree-ssa/cunroll-10.c =================================================================== --- testsuite/gcc.dg/tree-ssa/cunroll-10.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/cunroll-10.c (revision 0) @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -Warray-bounds -fdump-tree-cunroll" } */ +int a[3]; +int b[4]; +main() +{ + int i; + for (i=0;i<4;i++) + if (b[i]==2) + a[i]++; +} +/* { dg-final { scan-tree-dump-times 2 "Forced statement unreachable:" "cunroll" } } */ +/* { dg-final { cleanup-tree-dump "cunroll" } } */ Index: testsuite/gcc.dg/tree-ssa/cunroll-9.c =================================================================== --- testsuite/gcc.dg/tree-ssa/cunroll-9.c (revision 0) +++ testsuite/gcc.dg/tree-ssa/cunroll-9.c (revision 0) @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-cunrolli" } */ +int a[10]; +int b[11]; +t (int n) +{ + int i; + int sum = 0; + for (i = 0; i < n; i++) + { + if (i > 1000) + abort (); + if (q ()) + sum += a[i]; + else + sum += b[i]; + } + return sum; +} +/* { dg-final { scan-tree-dump-times 1 "Removed pointless exit:" "cunroli" } } */ +/* { dg-final { cleanup-tree-dump "cunroli" } } */