From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3935 invoked by alias); 3 Jan 2007 02:40:01 -0000 Received: (qmail 3926 invoked by uid 22791); 3 Jan 2007 02:40:00 -0000 X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.33.17) by sourceware.org (qpsmtpd/0.31) with ESMTP; Wed, 03 Jan 2007 02:39:55 +0000 Received: from spaceape11.eur.corp.google.com (spaceape11.eur.corp.google.com [172.28.16.145]) by smtp-out.google.com with ESMTP id l032dmtY011008 for ; Wed, 3 Jan 2007 02:39:49 GMT Received: from localhost (whippen.corp.google.com [172.18.117.13]) by spaceape11.eur.corp.google.com with ESMTP id l032dgDh019751; Wed, 3 Jan 2007 02:39:42 GMT Received: by localhost (Postfix, from userid 24751) id DA18E276DC0; Tue, 2 Jan 2007 18:39:38 -0800 (PST) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <17819.5994.111024.985123@whippen.corp.google.com> Date: Wed, 03 Jan 2007 02:40:00 -0000 To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fold more aggressively for trip counts X-Mailer: VM 7.19 under Emacs 21.4.1 Reply-To: Robert Kennedy From: jimbob@google.com (Robert Kennedy) 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: 2007-01/txt/msg00108.txt.bz2 Attached is a patch to do a little bit of extra work in analyzing trip counts for loops. As a side benefit, some other phases will perhaps get slightly better folding results. The motivation for this patch came from some experiments I did with doing strength reduction and linear function test replacement rather early in optimization, before, e.g., vectorization. At first, code introduced by SR caused some failures by keeping loops from being analyzed well, hence the genesis of this patch. Bootstrapped and tested on i686-pc-linux-gnu. -- Robert Kennedy ------------------------------ 2007-01-02 Robert Kennedy * tree-ssa-loop-niter.c (tree_simplify_using_condition_1): Simplify using simply related variables, not just identical ones. * fold-const.c (fold_comparison): Fold comparisons like (x * 1000 < 0) to (x < 0). ==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c#16 - /home/jimbob/clients/jimbob-perforce2-test/gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c ==== # action=edit type=text --- gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c 2006-12-21 16:55:26.000000000 -0800 +++ gcctools/google_vendor_src_branch/gcc/trunk/gcc/fold-const.c 2007-01-02 11:06:35.000000000 -0800 @@ -42,7 +42,7 @@ force_fit_type takes a constant, an overflowable flag and prior overflow indicators. It forces the value to fit the type and sets TREE_OVERFLOW and TREE_CONSTANT_OVERFLOW as appropriate. - + Note: Since the folders get called on non-gimple code as well as gimple code, we need to handle GIMPLE tuples as well as their corresponding tree equivalents. */ @@ -8065,6 +8065,29 @@ variable2); } + /* Transform comparisons of the form X * C1 CMP 0 to X CMP 0 in the + signed arithmetic case. That form is created by the compiler + often enough for folding it to be of value. One example is in + computing loop trip counts after Operator Strength Reduction. */ + if (!(flag_wrapv || flag_trapv) + && !TYPE_UNSIGNED (TREE_TYPE (arg0)) + && TREE_CODE (arg0) == MULT_EXPR + && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST + && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1))) + && integer_zerop (arg1)) + { + tree const1 = TREE_OPERAND (arg0, 1); + tree const2 = arg1; /* zero */ + tree variable1 = TREE_OPERAND (arg0, 0); + enum tree_code cmp_code = code; + + /* If const1 is negative we swap the sense of the comparison. */ + if (tree_int_cst_sgn (const1) < 0) + cmp_code = swap_tree_comparison (cmp_code); + + return fold_build2 (cmp_code, type, variable1, const2); + } + tem = maybe_canonicalize_comparison (code, type, arg0, arg1); if (tem) return tem; ==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c#10 - /home/jimbob/clients/jimbob-perforce2-test/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c ==== # action=edit type=text --- gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c 2006-12-29 11:18:58.000000000 -0800 +++ gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-loop-niter.c 2007-01-02 11:11:41.000000000 -0800 @@ -837,6 +837,55 @@ if (e && integer_zerop (e)) return e; + /* Try something a little aggressive: If te is easily expressible in + terms of a variable in cond (resp. notcond), we can give a + stronger answer. Get the definitions of te's variable(s) and try + checks based on equivalent (or weaker) conditions in terms of + them. The original motivation was to keep Operator Strength + Reduction from hurting subsequent loop optimizations by making + trip counts harder to compute. + + TODO: Consider iterating here through copies instead of checking + just one level up. */ + + if (COMPARISON_CLASS_P (te)) + { + tree def0; + tree def1; + + def0 = e0 = TREE_OPERAND (te, 0); + def1 = e1 = TREE_OPERAND (te, 1); + + /* Did somebody make sure te is canonicalized somehow? What are the + rules for its canonicalization? */ + if (TREE_CODE (e0) == SSA_NAME) + { + tree def = SSA_NAME_DEF_STMT (e0); + if (TREE_CODE (def) == GIMPLE_MODIFY_STMT) + def0 = GIMPLE_STMT_OPERAND (def, 1); + } + if (TREE_CODE (e1) == SSA_NAME) + { + tree def = SSA_NAME_DEF_STMT (e1); + if (TREE_CODE (def) == GIMPLE_MODIFY_STMT) + def1 = GIMPLE_STMT_OPERAND (def, 1); + } + + if (def0 != e0 + || def1 != e1) + te = fold_build2 (TREE_CODE (te), boolean_type_node, def0, def1); + + /* Check whether COND ==> EXPR. */ + e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te); + if (e && integer_nonzerop (e)) + return e; + + /* Check whether COND ==> not EXPR. */ + e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te); + if (e && integer_zerop (e)) + return e; + } + return expr; }