From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 569 invoked by alias); 3 Jan 2007 13:57:55 -0000 Received: (qmail 558 invoked by uid 22791); 3 Jan 2007 13:57:53 -0000 X-Spam-Check-By: sourceware.org Received: from nf-out-0910.google.com (HELO nf-out-0910.google.com) (64.233.182.188) by sourceware.org (qpsmtpd/0.31) with ESMTP; Wed, 03 Jan 2007 13:57:45 +0000 Received: by nf-out-0910.google.com with SMTP id a27so7564751nfc for ; Wed, 03 Jan 2007 05:57:43 -0800 (PST) Received: by 10.82.182.8 with SMTP id e8mr1343190buf.1167832663251; Wed, 03 Jan 2007 05:57:43 -0800 (PST) Received: by 10.82.150.13 with HTTP; Wed, 3 Jan 2007 05:57:43 -0800 (PST) Message-ID: <84fc9c000701030557y771149b5kb19643b0a50dd502@mail.gmail.com> Date: Wed, 03 Jan 2007 13:57:00 -0000 From: "Richard Guenther" To: "Robert Kennedy" Subject: Re: [PATCH] Fold more aggressively for trip counts Cc: gcc-patches@gcc.gnu.org In-Reply-To: <17819.5994.111024.985123@whippen.corp.google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <17819.5994.111024.985123@whippen.corp.google.com> X-IsSubscribed: yes 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/msg00127.txt.bz2 On 1/3/07, Robert Kennedy wrote: > 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. The fold-const change is ok if you add a testcase. tree_simplify_using_condition_1 is already complex, ugly and slow - we shouldn't add to that more. Can you provide a testcase and see where we create a comparison that makes this extra testing worthwhile? Can you fix this place instead? Thanks, Richard. > > -- 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; > } >