From patchwork Tue Jan 8 16:35:05 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 210432 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 22EDB2C0085 for ; Wed, 9 Jan 2013 03:35:32 +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=1358267733; 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=mLwH/YfOaK78BJ4vq8oL7jSu5Io=; b=gYQom59nEqmREis /7zZLPzTi5NQa8uaxl2wM7A1al6de/9lMPEbe1eX0LpEG1UE2Xt9UemSIMLX1ZRz TRSRGqXY0jIJZVQ4l03ZLWjVT+e9hq5OgONzCJFedQMOjlP77Vns3306U5xPOenB Uh7XgJwQToXR+Q2eT8soW2+fwpL0= 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=wT/2vlpWOSClEbGeNrBoMp2m1PCWWOe6sC8D7mF9dRxaArhnMFczqmU+w/lIq0 UphY/G5M6KwFO6seIS/XlL6drCpov2YJiUf1Q1LP+fbKSRiHcqaTmWcRc2rqndon iaA1QgyABBOzG8/EAG6d2if0SpgbEcL8oio8fSRU3xqsw=; Received: (qmail 31714 invoked by alias); 8 Jan 2013 16:35:22 -0000 Received: (qmail 31491 invoked by uid 22791); 8 Jan 2013 16:35:19 -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:35:07 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id B08A1542909; Tue, 8 Jan 2013 17:35:05 +0100 (CET) Date: Tue, 8 Jan 2013 17:35:05 +0100 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de, jakub@redhat.com Subject: PR 55875 (IV wrapping issue) Message-ID: <20130108163505.GB17341@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, My patch to add bounds that are not dominating loop latch caused problem in scev_probably_wraps_p that is trying to prove that given IV at given STMT is not wrapping based on loop bounds. When I was extending loop bounds to contain not only statements that dominate the loop latch, I verified the users that they are valid after the change. In this case it is however not true. What I missed is that it does two things 1) it tries to prove that STMT is bounded by given bound based on fact that bound's STMT dominate the statement 2) it tries to prove the bound based on number of iterations of loop that it derrives from the bounds I saw the dominance test in there and was happy. Obviously however 2) needs to be updated. It seems to me best to simply drop 2) that anyway is just determining a bound on number of iterations and use the bound recorded in the structure. While doing that I also noticed older problem in the postdominance test - we need to verify that loop is not terminated by a call or other side ffect as demonstrated by the new C testcase I constructed. This testcase probably fails in 4.7 and earlier releases. Boostrapped/regtested x86_64-linux Honza * 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,37 @@ 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)) { + 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. */ bound += double_int_one; if (bound.is_zero () || !double_int_fits_to_tree_p (nit_type, bound)) @@ -3640,10 +3652,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 +3720,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 ();