From patchwork Mon May 26 12:55:18 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 352508 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]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 5B9A11400C6 for ; Mon, 26 May 2014 22:55:31 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; q=dns; s=default; b=KyR0srpoahGDpe45AL QosWbuZ0wFsQnIIYUlRO5Qxkz2gOx0yckE+/1lCas+rlwQLjO07Gx6wgTx2ZCRBN 2s+MjED0HOtTxElZFxU47PUhcQj6DpelDcBW7dwhzMDxou3VbTlmQWYrWyHXhg1+ kOnQ2x1lqWC1WAKQgZ8tcZOVU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; s=default; bh=A5ZHQMjwjUyEAZtl9SKGE3wU Dxo=; b=eVBvEPqIE+U7GCeixRBRf0gIYJIBxYV4/sneqrFPdNCh4g7Eq//6cxNu 3zxHzMTnBInFGZ1A8SSRXCI4k7QJPVo3uwPMNZDtR4JACHUocdIQhSRPi0eDUh4h N+Ia0LlZIvPfTjhPTAKjX1AKR3qtToLaDMPTkAU8CgT2WYQkMp8= Received: (qmail 29253 invoked by alias); 26 May 2014 12:55:24 -0000 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 Received: (qmail 29235 invoked by uid 89); 26 May 2014 12:55:23 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=1.9 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, KAM_STOCKTIP, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=no version=3.3.2 X-HELO: mail-wi0-f181.google.com Received: from mail-wi0-f181.google.com (HELO mail-wi0-f181.google.com) (209.85.212.181) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 26 May 2014 12:55:22 +0000 Received: by mail-wi0-f181.google.com with SMTP id n15so4363429wiw.14 for ; Mon, 26 May 2014 05:55:19 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.194.82.170 with SMTP id j10mr29101391wjy.63.1401108918927; Mon, 26 May 2014 05:55:18 -0700 (PDT) Received: by 10.194.119.193 with HTTP; Mon, 26 May 2014 05:55:18 -0700 (PDT) In-Reply-To: <1466969.VvFMuDKXoD@polaris> References: <1466969.VvFMuDKXoD@polaris> Date: Mon, 26 May 2014 14:55:18 +0200 Message-ID: Subject: Re: [RFC] optimize x - y cmp 0 with undefined overflow From: Richard Biener To: Eric Botcazou Cc: GCC Patches X-IsSubscribed: yes On Mon, May 26, 2014 at 12:22 PM, Eric Botcazou wrote: > Hi, > > the motivation of this work is to get rid of the range check on Z in: > > function F (X : Integer; Y : Integer ) return Positive is > Z : Integer; > begin > if X >= Y then > return 1; > end if; > Z := Y - X; > return Z; > end; > > An equivalent C testcase is: > > extern void abort (void); > > int foo (int x, int y) > { > int z; > > if (x >= y) > return 1; > > z = y - x; > if (z <= 0) > abort (); > > return z; > } > > for which the call to abort is not optimized at -O2. > > > fold_comparison knows how to optimize X +- C1 CMP C2 to X CMP C2 -+ C1 with > undefined overflow so optimizing X - Y CMP 0 to X CMP Y is a generalization. > > Once this is done, forwprop will immediately optimize: > > extern void abort (void); > > int foo (int x, int y) > { > int z; > > if (x >= y) > return 1; > > z = y - x; > if (z <= 0) > abort (); > > return 0; > } > > because 'z' has a single use, but the original testcase won't be optimized. > > > The attached patch implements the missing bits in vrp_evaluate_conditional by > manual propagating the operands of a defining PLUS_EXPR or MINUS_EXPR for an > SSA name in a condition; an other possibility could be DOM instead of VRP. > > This comes with 4 testcases: the original Ada testcase, the C equivalent, a > testcase for the folding and another one for the -Wstrict-overflow warning. > > Tested on x86_64-suse-linux with no regressions. + tree new_const + = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, const1); /* If the constant operation overflowed this can be simplified as a comparison against INT_MAX/INT_MIN. */ - if (TREE_CODE (lhs) == INTEGER_CST - && TREE_OVERFLOW (lhs)) + if (TREE_OVERFLOW (new_const)) well, either use int_const_binop above or retain the check (or use TREE_OVERFLOW_P). Bonus points for using wide-ints here and not relying on TREE_OVERFLOW. + /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */ + if (TREE_CODE (arg0) == MINUS_EXPR + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)) any good reason for using TYPE_OVERFLOW_UNDEFINED on the type of arg1 instead on the type of the MINUS (yes, they should match, but it really looks odd ... the overflow of the minus has to be undefined). Also for EQ_EXPR and NE_EXPR the transform is fine even when !TYPE_OVERFLOW_UNDEFINED (and we seem to perform it already somewhere). Please look where and try to add the undefined overflow case to it. As for the VRP pieces I don't understand what is missing here (well, compare_range_with_value and/or compare_values might not handle this case? then better fix that to improve symbolic range handling in general?). Also I have a longstanding patch in my tree that does maybe that helps as well. Thanks, Richard. > > 2014-05-26 Eric Botcazou > > * fold-const.c (fold_comparison): Clean up and simplify X +- C1 CMP C2 > to X CMP C2 -+ C1 transformation, add X - Y CMP 0 to X CMP Y. > * tree-vrp.c (vrp_evaluate_conditional_warnv_with_fold): New function. > (vrp_evaluate_conditional): Call it on SSA names with defining PLUS_EXPR > or MINUS_EXPR if the evaluation of the condition yielded nothing. > > > 2014-05-26 Eric Botcazou > > * gcc.dg/fold-compare-8.c: New test. > * gcc.dg/Wstrict-overflow-25.c: Likewise. > * gcc.dg/tree-ssa/vrp92.c: Likewise. > * gnat.dg/opt38.adb: Likewise. > > > -- > Eric Botcazou Index: gcc/tree-vrp.c =================================================================== --- gcc/tree-vrp.c (revision 210931) +++ gcc/tree-vrp.c (working copy) @@ -6919,14 +6919,15 @@ vrp_evaluate_conditional_warnv_with_ops_ vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL; vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; + tree res = NULL_TREE; if (vr0 && vr1) - return compare_ranges (code, vr0, vr1, strict_overflow_p); - else if (vr0 && vr1 == NULL) - return compare_range_with_value (code, vr0, op1, strict_overflow_p); - else if (vr0 == NULL && vr1) - return (compare_range_with_value + res = compare_ranges (code, vr0, vr1, strict_overflow_p); + if (!res && vr0) + res = compare_range_with_value (code, vr0, op1, strict_overflow_p); + if (!res && vr1) + res = (compare_range_with_value (swap_tree_comparison (code), vr1, op0, strict_overflow_p)); - return NULL; + return res; } /* Helper function for vrp_evaluate_conditional_warnv. */