From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22837 invoked by alias); 3 Jun 2014 08:13:46 -0000 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 Received: (qmail 22821 invoked by uid 89); 3 Jun 2014 08:13:44 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.3.2 X-HELO: smtp.eu.adacore.com Received: from mel.act-europe.fr (HELO smtp.eu.adacore.com) (194.98.77.210) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Tue, 03 Jun 2014 08:13:43 +0000 Received: from localhost (localhost [127.0.0.1]) by filtered-smtp.eu.adacore.com (Postfix) with ESMTP id 92C9927E497C; Tue, 3 Jun 2014 10:13:40 +0200 (CEST) Received: from smtp.eu.adacore.com ([127.0.0.1]) by localhost (smtp.eu.adacore.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id sJmtxo3GHahJ; Tue, 3 Jun 2014 10:13:40 +0200 (CEST) Received: from polaris.localnet (bon31-6-88-161-99-133.fbx.proxad.net [88.161.99.133]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by smtp.eu.adacore.com (Postfix) with ESMTPSA id 6AD6E27E4973; Tue, 3 Jun 2014 10:13:40 +0200 (CEST) From: Eric Botcazou To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: Re: [RFC] optimize x - y cmp 0 with undefined overflow Date: Tue, 03 Jun 2014 08:13:00 -0000 Message-ID: <1624774.xzcp69eE4l@polaris> User-Agent: KMail/4.7.2 (Linux/3.1.10-1.29-desktop; KDE/4.7.2; x86_64; ; ) In-Reply-To: References: <1466969.VvFMuDKXoD@polaris> <2272943.QullF6hSsT@polaris> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="nextPart2302221.P0qsx73FFW" Content-Transfer-Encoding: 7Bit X-SW-Source: 2014-06/txt/msg00184.txt.bz2 --nextPart2302221.P0qsx73FFW Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Content-length: 3699 > Looks mostly ok. Any reason why you are not re-creating > MINUS_EXPR in build_symbolic_expr? That is, build > inv - t (for non-pointers, of course)? It's more uniform and compare_values expects an INTEGER_CST on the RHS, although the patch was lacking a small tweak to the function: @@ -1205,19 +1292,23 @@ compare_values_warnv (tree val1, tree va STRIP_USELESS_TYPE_CONVERSION (val2); if ((TREE_CODE (val1) == SSA_NAME + || (TREE_CODE (val1) == NEGATE_EXPR + && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME) || TREE_CODE (val1) == PLUS_EXPR || TREE_CODE (val1) == MINUS_EXPR) && (TREE_CODE (val2) == SSA_NAME + || (TREE_CODE (val2) == NEGATE_EXPR + && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME) || TREE_CODE (val2) == PLUS_EXPR || TREE_CODE (val2) == MINUS_EXPR)) { tree n1, c1, n2, c2; enum tree_code code1, code2; - /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', + /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME', return -1 or +1 accordingly. If VAL1 and VAL2 don't use the same name, return -2. */ - if (TREE_CODE (val1) == SSA_NAME) + if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR) { code1 = SSA_NAME; n1 = val1; @@ -1239,7 +1330,7 @@ compare_values_warnv (tree val1, tree va } } - if (TREE_CODE (val2) == SSA_NAME) + if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR) { code2 = SSA_NAME; n2 = val2; @@ -1262,6 +1353,11 @@ compare_values_warnv (tree val1, tree va } /* Both values must use the same name. */ + if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR) + { + n1 = TREE_OPERAND (n1, 0); + n2 = TREE_OPERAND (n2, 0); + } if (n1 != n2) return -2; > Otherwise if a range becomes -t + inv that will no longer match > get_single_symbol for further propagation? Yes, it will, NEGATE_EXPR is handled by get_single_symbol. > Then I'm not sure if > > + /* Try with VR0 and [-INF, OP1]. */ > + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, > NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, > &new_vr1); + if (vr->type != VR_VARYING) > + return; > + > + /* Try with VR0 and [OP1, +INF]. */ > + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), > NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, > &new_vr1); + if (vr->type != VR_VARYING) > + return; > > is a safe thing to do. If it does make a difference to try [-INF, OP1], > [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;) > (or an "easy" missed optimization). Yes, it makes a difference and is required to eliminate half-symbolic ranges (the ones deduced from x >= y). Otherwise extract_range_from_binary_expr_1 will reject the resulting range because it cannot compare the bounds. As discussed, extract_range_from_binary_expr_1 doesn't do any fiddling with the input ranges, it just computes the resulting range and see whether it can interpret it. Half-symbolic ranges cannot be interpreted and probably should not, in the general case at least, because I think it can be very delicate, so extract_range_from_binary_expr will just try all the possible combinations for PLUS and MINUS. The testcases were attached to the first message in the thread, but I presume that decent mail programs are a thing of the past. :-) Attached again. -- Eric Botcazou --nextPart2302221.P0qsx73FFW Content-Disposition: attachment; filename="opt38.adb" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="utf-8"; name="opt38.adb" Content-length: 345 -- { dg-do compile } -- { dg-options "-O2 -fdump-tree-optimized" } function Opt38 (X : Integer; Y : Integer ) return Positive is Z : Integer; begin if X >= Y then return 1; end if; Z := Y - X; return Z; end; -- { dg-final { scan-tree-dump-not "gnat_rcheck" "optimized" } } -- { dg-final { cleanup-tree-dump "optimized" } } --nextPart2302221.P0qsx73FFW Content-Disposition: attachment; filename="vrp93.c" Content-Transfer-Encoding: 7Bit Content-Type: text/x-csrc; charset="utf-8"; name="vrp93.c" Content-length: 495 /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ extern void abort (void); int foo1 (int x, int y) { int z; if (x >= y) return 1; z = y - x; if (z <= 0) abort (); return z; } unsigned int foo2 (unsigned int x, unsigned int y) { unsigned int z; if (x >= y) return 1; z = y - x; if (z == 0) abort (); return z; } /* { dg-final { scan-tree-dump-not "abort" "optimized" } } */ /* { dg-final { cleanup-tree-dump "optimized" } } */ --nextPart2302221.P0qsx73FFW--