From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8609 invoked by alias); 8 Jan 2013 16:49:40 -0000 Received: (qmail 8558 invoked by uid 22791); 8 Jan 2013 16:49:39 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,RCVD_IN_DNSWL_LOW,RP_MATCHES_RCVD,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; Tue, 08 Jan 2013 16:49:30 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 0A0F9542B22; Tue, 8 Jan 2013 17:49:28 +0100 (CET) Date: Tue, 08 Jan 2013 16:49:00 -0000 From: Jan Hubicka To: Jan Hubicka Cc: gcc-patches@gcc.gnu.org, rguenther@suse.de, jakub@redhat.com Subject: Re: PR 55875 (IV wrapping issue) Message-ID: <20130108164928.GA3891@kam.mff.cuni.cz> References: <20130108163505.GB17341@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20130108163505.GB17341@kam.mff.cuni.cz> 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-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2013-01/txt/msg00429.txt.bz2 Hi, I actually attached not completely final version of the patch. This one has the extra loop looking for side effect that cures the first testcase. Sorry for the confussion. Honza PR tree-optimize/55875 * gcc.c-torture/execute/pr55875.c: New testcase. * g++.dg/torture/pr55875.C: New testcase. * tree-ssa-loop-niter.c (n_of_executions_at_most): Simplify to only test for cases where statement is dominated by the particular bound; handle correctly the "postdominance" test. (scev_probably_wraps_p): Use max loop iterations info as a global bound first. Index: testsuite/gcc.c-torture/execute/pr55875.c =================================================================== --- testsuite/gcc.c-torture/execute/pr55875.c (revision 0) +++ testsuite/gcc.c-torture/execute/pr55875.c (revision 0) @@ -0,0 +1,17 @@ +int a[250]; +__attribute__ ((noinline)) +t(int i) +{ + if (i==0) + exit(0); + if (i>255) + abort (); +} +main() +{ + unsigned int i; + for (i=0;;i++) + { + a[i]=t((unsigned char)(i+5)); + } +} Index: testsuite/g++.dg/torture/pr55875.C =================================================================== --- testsuite/g++.dg/torture/pr55875.C (revision 0) +++ testsuite/g++.dg/torture/pr55875.C (revision 0) @@ -0,0 +1,53 @@ +struct A +{ + short int a1; + unsigned char a2; + unsigned int a3; +}; + +struct B +{ + unsigned short b1; + const A *b2; +}; + +B b; + +__attribute__((noinline, noclone)) +int foo (unsigned x) +{ + __asm volatile ("" : "+r" (x) : : "memory"); + return x; +} + +inline void +bar (const int &) +{ +} + +__attribute__((noinline)) void +baz () +{ + const A *a = b.b2; + unsigned int i; + unsigned short n = b.b1; + for (i = 0; i < n; ++i) + if (a[i].a1 == 11) + { + if (i > 0 && (a[i - 1].a2 & 1)) + continue; + bar (foo (2)); + return; + } +} + +int +main () +{ + A a[4] = { { 10, 0, 0 }, { 11, 1, 0 }, { 11, 1, 0 }, { 11, 1, 0 } }; + b.b1 = 4; + b.b2 = a; + baz (); + return 0; +} + Index: tree-ssa-loop-niter.c =================================================================== --- tree-ssa-loop-niter.c (revision 194918) +++ tree-ssa-loop-niter.c (working copy) @@ -3549,8 +3549,15 @@ stmt_dominates_stmt_p (gimple s1, gimple /* Returns true when we can prove that the number of executions of STMT in the loop is at most NITER, according to the bound on the number of executions of the statement NITER_BOUND->stmt recorded in - NITER_BOUND. If STMT is NULL, we must prove this bound for all - statements in the loop. */ + NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT. + + ??? This code can become quite a CPU hog - we can have many bounds, + and large basic block forcing stmt_dominates_stmt_p to be queried + many times on a large basic blocks, so the whole thing is O(n^2) + for scev_probably_wraps_p invocation (that can be done n times). + + It would make more sense (and give better answers) to remember BB + bounds computed by discover_iteration_bound_by_body_walk. */ static bool n_of_executions_at_most (gimple stmt, @@ -3571,32 +3578,43 @@ n_of_executions_at_most (gimple stmt, /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 times. This means that: - -- if NITER_BOUND->is_exit is true, then everything before - NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 - times, and everything after it at most NITER_BOUND->bound times. + -- if NITER_BOUND->is_exit is true, then everything after + it at most NITER_BOUND->bound times. -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT is executed, then NITER_BOUND->stmt is executed as well in the same - iteration (we conclude that if both statements belong to the same - basic block, or if STMT is after NITER_BOUND->stmt), then STMT - is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is - executed at most NITER_BOUND->bound + 2 times. */ + iteration then STMT is executed at most NITER_BOUND->bound + 1 times. + + If we can determine that NITER_BOUND->stmt is always executed + after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times. + We conclude that if both statements belong to the same + basic block and STMT is before NITER_BOUND->stmt and there are no + statements with side effects in between. */ if (niter_bound->is_exit) { - if (stmt - && stmt != niter_bound->stmt - && stmt_dominates_stmt_p (niter_bound->stmt, stmt)) - cmp = GE_EXPR; - else - cmp = GT_EXPR; + if (stmt == niter_bound->stmt + || !stmt_dominates_stmt_p (niter_bound->stmt, stmt)) + return false; + cmp = GE_EXPR; } else { - if (!stmt - || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt) - && !stmt_dominates_stmt_p (niter_bound->stmt, stmt))) + if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt)) { + gimple_stmt_iterator bsi; + if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt) + || gimple_code (stmt) == GIMPLE_PHI + || gimple_code (niter_bound->stmt) == GIMPLE_PHI) + return false; + + /* By stmt_dominates_stmt_p we already know that STMT appears + before NITER_BOUND->STMT. Still need to test that the loop + can not be terinated by a side effect in between. */ + for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt; + gsi_next (&bsi)) + if (gimple_has_side_effects (gsi_stmt (bsi))) + return false; bound += double_int_one; if (bound.is_zero () || !double_int_fits_to_tree_p (nit_type, bound)) @@ -3640,10 +3658,12 @@ scev_probably_wraps_p (tree base, tree s gimple at_stmt, struct loop *loop, bool use_overflow_semantics) { - struct nb_iter_bound *bound; tree delta, step_abs; tree unsigned_type, valid_niter; tree type = TREE_TYPE (step); + tree e; + double_int niter; + struct nb_iter_bound *bound; /* FIXME: We really need something like http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. @@ -3706,14 +3726,26 @@ scev_probably_wraps_p (tree base, tree s valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); estimate_numbers_of_iterations_loop (loop); - for (bound = loop->bounds; bound; bound = bound->next) + + if (max_loop_iterations (loop, &niter) + && double_int_fits_to_tree_p (TREE_TYPE (valid_niter), niter) + && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter, + double_int_to_tree (TREE_TYPE (valid_niter), + niter))) != NULL + && integer_nonzerop (e)) { - if (n_of_executions_at_most (at_stmt, bound, valid_niter)) - { - fold_undefer_and_ignore_overflow_warnings (); - return false; - } + fold_undefer_and_ignore_overflow_warnings (); + return false; } + if (at_stmt) + for (bound = loop->bounds; bound; bound = bound->next) + { + if (n_of_executions_at_most (at_stmt, bound, valid_niter)) + { + fold_undefer_and_ignore_overflow_warnings (); + return false; + } + } fold_undefer_and_ignore_overflow_warnings ();