From patchwork Thu Mar 8 14:29:11 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ulrich Weigand X-Patchwork-Id: 145536 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 AFF80B6F9D for ; Fri, 9 Mar 2012 01:30:22 +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=1331821823; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:Message-Id:Received:Subject:To:Date: From:Cc:In-Reply-To:MIME-Version:Content-Type: Content-Transfer-Encoding:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=BUx45WaW6Mkh5X6P7EFH03dMJ78=; b=dAI4ofGlmSYfHKl aWs56w+8AJFMBowIlKzvA7komIpNLPqoMZvN+x+hx6K74dfCRAswa4x2/Nw6vhMt vEls2HvhkRzwdqphLssk4LwlVD+f+c0B5hz07/zFQIapeotcI7i+2DmAde8eiOet 0/A/VHAN6MH5PtJEkyRCbkJFk7CU= 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:Received:Received:Received:Received:Message-Id:Received:Subject:To:Date:From:Cc:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding:x-cbid:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=S85MjxeLjmSfwr20G22CLWoK1egfbcDvHz2721fT79kQsltLDTX5YtzQNpggGc l/uv08wtisGOQsHzusR7cgmt7DTQZ7tQcHZFzyaKtmmlrPM2UP8lmH3k/qvM1i1l V7kFX2X4uVEhDX+xBHc01Rf2pgLtJJE85sa20um4/5v3k=; Received: (qmail 5386 invoked by alias); 8 Mar 2012 14:30:08 -0000 Received: (qmail 5325 invoked by uid 22791); 8 Mar 2012 14:30:03 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, MSGID_FROM_MTA_HEADER, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from e06smtp17.uk.ibm.com (HELO e06smtp17.uk.ibm.com) (195.75.94.113) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 08 Mar 2012 14:29:44 +0000 Received: from /spool/local by e06smtp17.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Thu, 8 Mar 2012 14:29:42 -0000 Received: from d06nrmr1806.portsmouth.uk.ibm.com (9.149.39.193) by e06smtp17.uk.ibm.com (192.168.101.147) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Thu, 8 Mar 2012 14:29:13 -0000 Received: from d06av02.portsmouth.uk.ibm.com (d06av02.portsmouth.uk.ibm.com [9.149.37.228]) by d06nrmr1806.portsmouth.uk.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id q28ETC4j2785388 for ; Thu, 8 Mar 2012 14:29:12 GMT Received: from d06av02.portsmouth.uk.ibm.com (loopback [127.0.0.1]) by d06av02.portsmouth.uk.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id q28ETCxP000879 for ; Thu, 8 Mar 2012 07:29:12 -0700 Received: from tuxmaker.boeblingen.de.ibm.com (tuxmaker.boeblingen.de.ibm.com [9.152.85.9]) by d06av02.portsmouth.uk.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with SMTP id q28ETB5T000824; Thu, 8 Mar 2012 07:29:11 -0700 Message-Id: <201203081429.q28ETB5T000824@d06av02.portsmouth.uk.ibm.com> Received: by tuxmaker.boeblingen.de.ibm.com (sSMTP sendmail emulation); Thu, 08 Mar 2012 15:29:11 +0100 Subject: Re: [WIP PATCH] Re: Inefficient end-of-loop value computation - missed optimization somewhere? To: richard.guenther@gmail.com (Richard Guenther) Date: Thu, 8 Mar 2012 15:29:11 +0100 (CET) From: "Ulrich Weigand" Cc: gcc-patches@gcc.gnu.org In-Reply-To: from "Richard Guenther" at Feb 28, 2012 04:23:44 PM MIME-Version: 1.0 x-cbid: 12030814-0542-0000-0000-000001363CD3 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 Richard Guenther wrote: > On Tue, Feb 28, 2012 at 4:10 PM, Ulrich Weigand wrote: > > I'll still need to do proper testing and benchmarking, but I thought > > I'd post the patch anyway just as a heads-up ... > > > > Does this look reasonable to you? > > Yes, that looks reasonable. Though instead of unsigned_type_for > please use build_nonstandard_integer_type instead (if the type > is not already unsigned). unsigned_type_for does not necessarily > preserve type-precision and may even return NULL. OK, I've changed the patch to use build_nonstandard_integer_type, and it still fixes the original problem. However, on further examination it turns out that this "fix" is not because the expression is actually simplified at tree level. Rather, it is just that because of some minor reassociation (the +1 is moved to the end), the *RTL* optimizers now see a (just as complex but) slightly different RTL sequence, and therefore combine now just happens to be able to fold everything together (using the RTL-level simplify_plus_minus machinery). Even worse, the patch causes a number of regressions: > FAIL: gcc.dg/tree-ssa/loop-15.c scan-tree-dump-times optimized "\\+" 0 > FAIL: gcc.dg/tree-ssa/loop-15.c scan-tree-dump-times optimized "n_. \\* n_." 1 > FAIL: gcc.dg/vect/no-scevccp-noreassoc-outer-4.c scan-tree-dump-times vect "OUTER LOOP VECTORIZED." 1 The loop-15.c problem is probably just a missed optimization elsewhere that can be fixed. The problem is that a loop-end value used to be computed as "(n - 1) * n + n" which got simplified via fold_plusminus_mult_expr to "n * n". When computing in unsigned, however, the expression becomes something along the lines of "[...] * (unsigned) n + (unsigned) n" and the top-level of fold_binary_loc removes the *outermost* NOP_EXPRs resulting in "[...] * (unsigned) n + n" which fold_plusminus_mult_expr no longer recognizes as something it can handle (since "(unsigned) n" is not operand_equal_p to "n"). I think this can be fixed by having fold_plusminus_mult_expr call STRIP_NOPS on sub-operands, as is already done elsewhere in fold_binary_loc. This basically fixes the test case (due to some remaining casts, the scan-tree-dump patterns still don't match as-is, but the expected code is again generated). The no-scevccp-noreassoc-outer-4.c problem is more difficult, and would seem to point to a fundamental problem with performing the computation in unsigned mode. In this case, the end value of an inner loop forms part of a scalar evolution of the outer loop. When computing the end value in unsigned type, that scalar evolution is no longer detected. In part, this is because the scalar evolution machinery might need to be improved in handling casts. In particular, in some places it only does STRIP_USELESS_TYPE_CONVERSION; changing those to STRIP_NOPS makes it detect the evolution again. But I'm not fully convinced this is a safe change ... In any case, this still doesn't make the outer loop vectorizable, since it is no longer provably finite. Without the patch, this could be proven *because* the computation of the inner loop's end value used signed arithmetic which cannot overflow. By performing the computation in unsigned, this information is in fact lost. This would seem to indicate that unconditionally using unsigned arithmetic even if not strictly necessary might not always be the best solution either. I've gone back and looked that at the original problem that (start + 1) + (int)((unsigned int) ~start + (unsigned int) end) is not simplified by fold-const. Interestingly enough, it *is* valid to simplify this expression to just plain "end", even with signed arithmetic, since the transformation does not introduce any new potential overflows. This is actually recognized in fold_binary_loc, but only one special case. See the code around the following comment: /* The only case we can still associate with two variables is if they are the same, modulo negation. */ Unfortunately, this handles only A and -A; it doesn't recognize that A+1 is in fact the negation of ~A ... There is also code in tree-ssa-forwprop.c:associate_plusminus that handles quite a number of special cases where re-association *is* allowed even for signed arithmetic: (A +- B) - A -> +- B (A +- B) -+ B -> A (CST +- A) +- CST -> CST +- A (A + CST) +- CST -> A + CST ~A + A -> -1 ~A + 1 -> -A A - (A +- B) -> -+ B A +- (B +- A) -> +- B CST +- (CST +- A) -> CST +- A CST +- (A +- CST) -> CST +- A A + ~A -> -1 This handles some cases involving ~, but still not quite the case we need for this expression. In addition, the forward propagtion logic doesn't seem to handle casts very well (as opposed to fold-const, which makes liberal use of STRIP_NOPS). I'm wondering where to go from there: - Why are those special re-association cases handled only in forwprop, and not in fold-cost? I would have expected forwprop to just propagate subexpressions into a tree and then use fold-const to actually simplify ... - Should I try to improve forwprop to handle casts and additional re- association cases until it handles the above expression? - Or should the logic in fold-const be improved to add additional cases of re-association? Thanks for any further suggestions! I've attached some of the changes mentioned above for reference. Bye, Ulrich Patch: Compute loop-end value using unsigned type. Index: gcc/tree-scalar-evolution.c =================================================================== --- gcc/tree-scalar-evolution.c (revision 184625) +++ gcc/tree-scalar-evolution.c (working copy) @@ -474,11 +474,22 @@ return chrec_dont_know; else { + tree type = TREE_TYPE (evolution_fn), utype = type; tree res; + /* Since the number of iterations is always unsigned, we perform + the computation in an unsigned type (if feasible) to allow for + improved simplification of subexpressions. */ + if ((INTEGRAL_TYPE_P (type) && !TYPE_UNSIGNED (type)) + || POINTER_TYPE_P (type)) + utype = build_nonstandard_integer_type + (TYPE_PRECISION (type), 1); + /* evolution_fn is the evolution function in LOOP. Get its value in the nb_iter-th iteration. */ - res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); + res = chrec_convert (utype, evolution_fn, NULL); + res = chrec_apply (inner_loop->num, res, nb_iter); + res = chrec_convert (type, res, NULL); if (chrec_contains_symbols_defined_in_loop (res, loop->num)) res = instantiate_parameters (loop, res); Patch: Use STRIP_NOPS on subexpressions in fold_plusminus_mult_expr Index: gcc/fold-const.c =================================================================== --- gcc/fold-const.c (revision 184625) +++ gcc/fold-const.c (working copy) @@ -7081,6 +7081,8 @@ { arg00 = TREE_OPERAND (arg0, 0); arg01 = TREE_OPERAND (arg0, 1); + STRIP_NOPS (arg00); + STRIP_NOPS (arg01); } else if (TREE_CODE (arg0) == INTEGER_CST) { @@ -7099,6 +7101,8 @@ { arg10 = TREE_OPERAND (arg1, 0); arg11 = TREE_OPERAND (arg1, 1); + STRIP_NOPS (arg10); + STRIP_NOPS (arg11); } else if (TREE_CODE (arg1) == INTEGER_CST) { Patch: Use STRIP_NOPS when following scalar evolutions Index: gcc/tree-scalar-evolution.c =================================================================== --- gcc/tree-scalar-evolution.c (revision 184625) +++ gcc/tree-scalar-evolution.c (working copy) @@ -1154,8 +1165,8 @@ rhs0 = TREE_OPERAND (expr, 0); rhs1 = TREE_OPERAND (expr, 1); type = TREE_TYPE (rhs0); - STRIP_USELESS_TYPE_CONVERSION (rhs0); - STRIP_USELESS_TYPE_CONVERSION (rhs1); + STRIP_NOPS (rhs0); + STRIP_NOPS (rhs1); res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1, halting_phi, evolution_of_loop, limit); break; @@ -1168,8 +1179,8 @@ rhs0 = TREE_OPERAND (expr, 0); rhs1 = TREE_OPERAND (expr, 1); type = TREE_TYPE (rhs0); - STRIP_USELESS_TYPE_CONVERSION (rhs0); - STRIP_USELESS_TYPE_CONVERSION (rhs1); + STRIP_NOPS (rhs0); + STRIP_NOPS (rhs1); res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, POINTER_PLUS_EXPR, rhs1, halting_phi, evolution_of_loop, limit);