From patchwork Mon Mar 4 21:28:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ken Matsui X-Patchwork-Id: 1907893 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=LJjIB+sA; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4TpX0b3z9Qz23cm for ; Tue, 5 Mar 2024 08:30:05 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 960D23858C55 for ; Mon, 4 Mar 2024 21:30:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 960D23858C55 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1709587803; bh=qhTv3z8t8rG7GLeiV07Pp8JS5ItpEb1Ys2JAqOpC7KU=; h=From:To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From; b=LJjIB+sAQDkdHYXemivPm+gGMcPijDOciuCJf10/JGrPddYL/7gfRkxeyfdLi52a+ C7tCHT16Djq7k8dIRtc7FsWW5J7hbeP/xJSLig38Me3cDsr87wLRlYRgwEAZTjM5hj 6kNe3O5XhZwVjsy+xkIAjlszzY8a720EuAwQR8o8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0b-00641c01.pphosted.com (mx0b-00641c01.pphosted.com [205.220.177.146]) by sourceware.org (Postfix) with ESMTPS id DE50B3858D28; Mon, 4 Mar 2024 21:29:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DE50B3858D28 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=gcc.gnu.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org DE50B3858D28 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=205.220.177.146 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1709587778; cv=none; b=TslefM8C41ixqbCDsjBbfuF9XhknsHk+JMFYtb5I9X3mnw29eIKc6Ng32wwAb8QU8AXoI59MwwLfmoQu2DLhz8U7mrmdraK0O7kDQwZtoaJCv9jYK370kWQ9fkLCba5h8NmjSNAqXj/Z67R5BS7gY8sn3CfeknJtUZ6+pRJ0j1U= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1709587778; c=relaxed/simple; bh=Y28Ym8tNPI65W9b47XmJFar4+tPijfuLBHYV5cqfVrA=; h=From:To:Subject:Date:Message-ID:MIME-Version; b=aFqQNfPO8BbK8SSQetlWSPNw0n+CD6ynk0fyzlOfIoJU3kug+7gUenVEa81/bLs9HTyMlS/m6T7E5M6kx8ce1OR9Rhip+nzYRN/KnV0ioyRB2FLTiNxcUyy5Koj+aU+zijAo4CvcK/EkAojr8uGfzs1XDQiJU4o/kidaoMmjEPM= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from pps.filterd (m0247477.ppops.net [127.0.0.1]) by mx0a-00641c01.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 424LR7TE009924; Mon, 4 Mar 2024 21:29:34 GMT Received: from mxout26.s.uw.edu (mxout26.s.uw.edu [140.142.234.176]) by mx0a-00641c01.pphosted.com (PPS) with ESMTPS id 3wnhdhkchc-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Mon, 04 Mar 2024 21:29:34 +0000 Received: from smtp.washington.edu (smtp.washington.edu [128.208.60.132]) by mxout26.s.uw.edu (8.14.4+UW20.07/8.14.4+UW24.02) with ESMTP id 424LT2Do020498 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 4 Mar 2024 13:29:02 -0800 X-Auth-Received: from kmatsui-ThinkPad-X1-Carbon-Gen-9.dhcp4.washington.edu ([10.154.74.128]) (authenticated authid=kmatsui) by smtp.washington.edu (8.16.1+UW21.10/8.14.4+UW24.02) with ESMTPSA id 424LT2xZ029227 (version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Mon, 4 Mar 2024 13:29:02 -0800 X-UW-Orig-Sender: kmatsui@smtp.washington.edu From: Ken Matsui To: gcc-patches@gcc.gnu.org Cc: Ken Matsui Subject: [PATCH v2] middle-end/113680 - Optimize (x - y) CMP 0 as x CMP y Date: Mon, 4 Mar 2024 13:28:58 -0800 Message-ID: <20240304212858.22263-1-kmatsui@gcc.gnu.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240304203830.3740968-1-kmatsui@gcc.gnu.org> References: <20240304203830.3740968-1-kmatsui@gcc.gnu.org> MIME-Version: 1.0 X-Proofpoint-ORIG-GUID: nxsD2fKAkv2MROw3Hf-8ZYZVO162hHP- X-Proofpoint-GUID: nxsD2fKAkv2MROw3Hf-8ZYZVO162hHP- X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.272,Aquarius:18.0.1011,Hydra:6.0.619,FMLib:17.11.176.26 definitions=2024-03-04_17,2024-03-04_01,2023-05-22_02 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 phishscore=0 clxscore=1034 spamscore=0 priorityscore=1501 adultscore=0 mlxscore=0 impostorscore=0 malwarescore=0 bulkscore=0 suspectscore=0 mlxlogscore=999 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2311290000 definitions=main-2403040166 X-Spam-Status: No, score=-13.1 required=5.0 tests=BAYES_00, GIT_PATCH_0, JMQ_SPF_NEUTRAL, KAM_DMARC_STATUS, KAM_SHORT, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NEUTRAL, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org (x - y) CMP 0 is equivalent to x CMP y where x and y are signed integers and CMP is <, <=, >, or >=. Similarly, 0 CMP (x - y) is equivalent to y CMP x. As reported in PR middle-end/113680, this equivalence does not hold for types other than signed integers. When it comes to conditions, the former was translated to a combination of sub and test, whereas the latter was translated to a single cmp. Thus, this optimization pass tries to optimize the former to the latter. When `-fwrapv` is enabled, GCC treats the overflow of signed integers as defined behavior, specifically, wrapping around according to two's complement arithmetic. This has implications for optimizations that rely on the standard behavior of signed integers, where overflow is undefined. Consider the example given: long long llmax = __LONG_LONG_MAX__; long long llmin = -llmax - 1; Here, `llmax - llmin` effectively becomes `llmax - (-llmax - 1)`, which simplifies to `2 * llmax + 1`. Given that `llmax` is the maximum value for a `long long`, this calculation overflows in a defined manner (wrapping around), which under `-fwrapv` is a legal operation that produces a negative value due to two's complement wraparound. Therefore, `llmax - llmin < 0` is true. However, the direct comparison `llmax < llmin` is false since `llmax` is the maximum possible value and `llmin` is the minimum. Hence, optimizations that rely on the equivalence of `(x - y) CMP 0` to `x CMP y` (and vice versa) cannot be safely applied when `-fwrapv` is enabled. This is why this optimization pass is disabled under `-fwrapv`. This optimization pass must run before the Jump Threading pass and the VRP pass, as it may modify conditions. For example, in the VRP pass: (1) int diff = x - y; if (diff > 0) foo(); if (diff < 0) bar(); The second condition would be converted to diff != 0 in the VRP pass because we know the postcondition of the first condition is diff <= 0, and then diff != 0 is cheaper than diff < 0. If we apply this pass after this VRP, we get: (2) int diff = x - y; if (x > y) foo(); if (diff != 0) bar(); This generates sub and test for the second condition and cmp for the first condition. However, if we apply this pass beforehand, we simply get: (3) int diff = x - y; if (x > y) foo(); if (x < y) bar(); In this code, diff will be eliminated as a dead code, and sub and test will not be generated, which is more efficient. For the Jump Threading pass, without this optimization pass, (1) and (3) above are recognized as different, which prevents TCO. PR middle-end/113680 gcc/ChangeLog: * Makefile.in: Add tree-ssa-cmp.o to OBJS. * common.opt: Define ftree-cmp * doc/invoke.texi: Document ftree-cmp. * opts.cc (default_options_table): Handle OPT_ftree_cmp. * passes.def (pass_cmp): New optimization pass. * timevar.def (TV_TREE_CMP): New variable for timing. * tree-pass.h (make_pass_cmp): New declaration. * tree-ssa-cmp.cc: New file. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr113680.c: New test. Signed-off-by: Ken Matsui --- gcc/Makefile.in | 1 + gcc/common.opt | 4 + gcc/doc/invoke.texi | 11 +- gcc/opts.cc | 1 + gcc/passes.def | 3 + gcc/testsuite/gcc.dg/tree-ssa/pr113680.c | 47 ++++ gcc/timevar.def | 1 + gcc/tree-pass.h | 1 + gcc/tree-ssa-cmp.cc | 262 +++++++++++++++++++++++ 9 files changed, 330 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr113680.c create mode 100644 gcc/tree-ssa-cmp.cc diff --git a/gcc/Makefile.in b/gcc/Makefile.in index a74761b7ab3..935b80b6947 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1731,6 +1731,7 @@ OBJS = \ tree-ssa-address.o \ tree-ssa-alias.o \ tree-ssa-ccp.o \ + tree-ssa-cmp.o \ tree-ssa-coalesce.o \ tree-ssa-copy.o \ tree-ssa-dce.o \ diff --git a/gcc/common.opt b/gcc/common.opt index 51c4a17da83..7c853224458 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -3053,6 +3053,10 @@ ftree-ch Common Var(flag_tree_ch) Optimization Enable loop header copying on trees. +ftree-cmp +Common Var(flag_tree_cmp) Optimization +Enable SSA comparison optimization on trees. + ftree-coalesce-inlined-vars Common Ignore RejectNegative Does nothing. Preserved for backward compatibility. diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index bdf05be387d..04762d490a3 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -619,7 +619,7 @@ Objective-C and Objective-C++ Dialects}. -fsplit-wide-types -fsplit-wide-types-early -fssa-backprop -fssa-phiopt -fstdarg-opt -fstore-merging -fstrict-aliasing -fipa-strict-aliasing -fthread-jumps -ftracer -ftree-bit-ccp --ftree-builtin-call-dce -ftree-ccp -ftree-ch +-ftree-builtin-call-dce -ftree-ccp -ftree-ch -ftree-cmp -ftree-coalesce-vars -ftree-copy-prop -ftree-dce -ftree-dominator-opts -ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting -ftree-loop-if-convert -ftree-loop-im @@ -12377,6 +12377,7 @@ compilation time. -ftree-bit-ccp -ftree-ccp -ftree-ch +-ftree-cmp -ftree-coalesce-vars -ftree-copy-prop -ftree-dce @@ -13707,6 +13708,14 @@ effectiveness of code motion optimizations. It also saves one jump. This flag is enabled by default at @option{-O1} and higher. It is not enabled for @option{-Os}, since it usually increases code size. +@opindex ftree-cmp +@item -ftree-cmp +Perform comparison optimization on trees. This decreases unnecessary +instructions for comparisons. This flag is enabled by default at +@option{-O1} and higher. This optimization is automatically disabled when +@option{-fwrapv} is specified to ensure correct behavior under signed integer +overflow wrapping. + @opindex ftree-loop-optimize @item -ftree-loop-optimize Perform loop optimizations on trees. This flag is enabled by default diff --git a/gcc/opts.cc b/gcc/opts.cc index 3333600e0ea..9ee64a48313 100644 --- a/gcc/opts.cc +++ b/gcc/opts.cc @@ -589,6 +589,7 @@ static const struct default_options default_options_table[] = { OPT_LEVELS_1_PLUS, OPT_ftree_builtin_call_dce, NULL, 1 }, { OPT_LEVELS_1_PLUS, OPT_ftree_ccp, NULL, 1 }, { OPT_LEVELS_1_PLUS, OPT_ftree_ch, NULL, 1 }, + { OPT_LEVELS_1_PLUS, OPT_ftree_cmp, NULL, 1 }, { OPT_LEVELS_1_PLUS, OPT_ftree_coalesce_vars, NULL, 1 }, { OPT_LEVELS_1_PLUS, OPT_ftree_copy_prop, NULL, 1 }, { OPT_LEVELS_1_PLUS, OPT_ftree_dce, NULL, 1 }, diff --git a/gcc/passes.def b/gcc/passes.def index 1cbbd413097..e28a2d3c309 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -84,6 +84,9 @@ along with GCC; see the file COPYING3. If not see /* After CCP we rewrite no longer addressed locals into SSA form if possible. */ NEXT_PASS (pass_forwprop); + /* Do cmp before early_thread_jumps and vrp since it may + modify conditions. */ + NEXT_PASS (pass_cmp); NEXT_PASS (pass_early_thread_jumps, /*first=*/true); NEXT_PASS (pass_sra_early); /* pass_build_ealias is a dummy pass that ensures that we diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr113680.c b/gcc/testsuite/gcc.dg/tree-ssa/pr113680.c new file mode 100644 index 00000000000..59cd865aa21 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr113680.c @@ -0,0 +1,47 @@ +/* { dg-do compile } */ +/* { dg-options "-Os -fdump-tree-optimized" } */ + +volatile int i = 0; + +void foo() { i = 1; } +void bar() { i = 2; } + +void f1(int x, int y) +{ + int diff = x - y; + if (diff > 0) + foo(); + if (diff < 0) + bar(); +} + +void f2(int x, int y) +{ + if ((x - y) > 0) + foo(); + if ((x - y) < 0) + bar(); +} + +void f3(int x, int y) +{ + if (x > y) + foo(); + if (x < y) + bar(); +} + +void f4(int x, int y) +{ + int diff = x - y; + if (diff > 0) + foo(); + if (x < y) + bar(); +} + +/* { dg-final { scan-tree-dump-not " - " "optimized" } } */ +/* { dg-final { scan-assembler-times "cmp" 1 { target { i?86-*-* x86_64-*-* } } } } */ +/* { dg-final { scan-assembler-times "jmp\[ \t\]+f1" 3 { target { i?86-*-* x86_64-*-* } } } } */ +/* { dg-final { scan-assembler-not "sub" { target { i?86-*-* x86_64-*-* } } } } */ +/* { dg-final { scan-assembler-not "test" { target { i?86-*-* x86_64-*-* } } } } */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 8e2168e0817..468266d0c56 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -157,6 +157,7 @@ DEFTIMEVAR (TV_TREE_EH , "tree eh") DEFTIMEVAR (TV_TREE_CFG , "tree CFG construction") DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanup") DEFTIMEVAR (TV_TREE_TAIL_MERGE , "tree tail merge") +DEFTIMEVAR (TV_TREE_CMP , "tree cmp") DEFTIMEVAR (TV_TREE_VRP , "tree VRP") DEFTIMEVAR (TV_TREE_VRP_THREADER , "tree VRP threader") DEFTIMEVAR (TV_TREE_EARLY_VRP , "tree Early VRP") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 29267589eeb..71789a279c0 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -401,6 +401,7 @@ extern gimple_opt_pass *make_pass_ch (gcc::context *ctxt); extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt); extern gimple_opt_pass *make_pass_sccopy (gcc::context *ctxt); extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_cmp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_split_paths (gcc::context *ctxt); extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt); extern gimple_opt_pass *make_pass_build_alias (gcc::context *ctxt); diff --git a/gcc/tree-ssa-cmp.cc b/gcc/tree-ssa-cmp.cc new file mode 100644 index 00000000000..41d4a58a5b5 --- /dev/null +++ b/gcc/tree-ssa-cmp.cc @@ -0,0 +1,262 @@ +/* Global, SSA-based optimizations using comparison identities. + Copyright (C) 2024 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +/* (x - y) CMP 0 is equivalent to x CMP y where x and y are signed integers and + CMP is <, <=, >, or >=. Similarly, 0 CMP (x - y) is equivalent to y CMP x. + As reported in PR middle-end/113680, this equivalence does not hold for + types other than signed integers. When it comes to conditions, the former + was translated to a combination of sub and test, whereas the latter was + translated to a single cmp. Thus, this optimization pass tries to optimize + the former to the latter. + + When `-fwrapv` is enabled, GCC treats the overflow of signed integers as + defined behavior, specifically, wrapping around according to two's + complement arithmetic. This has implications for optimizations that + rely on the standard behavior of signed integers, where overflow is + undefined. Consider the example given: + + long long llmax = __LONG_LONG_MAX__; + long long llmin = -llmax - 1; + + Here, `llmax - llmin` effectively becomes `llmax - (-llmax - 1)`, which + simplifies to `2 * llmax + 1`. Given that `llmax` is the maximum value for + a `long long`, this calculation overflows in a defined manner + (wrapping around), which under `-fwrapv` is a legal operation that produces + a negative value due to two's complement wraparound. Therefore, + `llmax - llmin < 0` is true. + + However, the direct comparison `llmax < llmin` is false since `llmax` is the + maximum possible value and `llmin` is the minimum. Hence, optimizations + that rely on the equivalence of `(x - y) CMP 0` to `x CMP y` (and vice versa) + cannot be safely applied when `-fwrapv` is enabled. This is why this + optimization pass is disabled under `-fwrapv`. + + This optimization pass must run before the Jump Threading pass and + the VRP pass, as it may modify conditions. For example, in the VRP pass: + + (1) + int diff = x - y; + if (diff > 0) + foo(); + if (diff < 0) + bar(); + + The second condition would be converted to diff != 0 in the VRP pass because + we know the postcondition of the first condition is diff <= 0, and then + diff != 0 is cheaper than diff < 0. If we apply this pass after this VRP, + we get: + + (2) + int diff = x - y; + if (x > y) + foo(); + if (diff != 0) + bar(); + + This generates sub and test for the second condition and cmp for the first + condition. However, if we apply this pass beforehand, we simply get: + + (3) + int diff = x - y; + if (x > y) + foo(); + if (x < y) + bar(); + + In this code, diff will be eliminated as a dead code, and sub and test will + not be generated, which is more efficient. + + For the Jump Threading pass, without this optimization pass, (1) and (3) + above are recognized as different, which prevents TCO. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-iterator.h" +#include "domwalk.h" + +/* True if VAR is a signed integer, false otherwise. */ + +static bool +is_signed_integer(const_tree var) +{ + return (TREE_CODE (TREE_TYPE (var)) == INTEGER_TYPE + && !TYPE_UNSIGNED (TREE_TYPE (var))); +} + +/* If EXPR is an integer zero, return it. If EXPR is SSA_NAME, and its + defining statement is a subtraction of two signed integers, return the + MINUS_EXPR. Otherwise, return NULL_TREE. */ + +static const_tree +prop_integer_zero_or_minus_expr (const_tree expr) +{ + if (integer_zerop (expr)) + return expr; + + if (TREE_CODE (expr) != SSA_NAME) + return NULL_TREE; + + gimple *defining_stmt = SSA_NAME_DEF_STMT (expr); + if (!is_gimple_assign (defining_stmt) + || gimple_assign_rhs_code (defining_stmt) != MINUS_EXPR) + return NULL_TREE; + + tree rhs1 = gimple_assign_rhs1 (defining_stmt); + if (!is_signed_integer (rhs1)) + return NULL_TREE; + + tree rhs2 = gimple_assign_rhs2 (defining_stmt); + if (!is_signed_integer (rhs2)) + return NULL_TREE; + + return build2 (MINUS_EXPR, TREE_TYPE (expr), rhs1, rhs2); +} + +/* Optimize: + + 1. (x - y) CMP 0 + 2. 0 CMP (x - y) + + to: + + 1. x CMP y + 2. y CMP x + + where CMP is either <, <=, >, or >=. */ + +static void +optimize_signed_comparison (gcond *stmt) +{ + const enum tree_code code = gimple_cond_code (stmt); + if (code < LT_EXPR || GE_EXPR < code) + return; + + const_tree lhs = prop_integer_zero_or_minus_expr (gimple_cond_lhs (stmt)); + if (lhs == NULL_TREE) + return; + + const_tree rhs = prop_integer_zero_or_minus_expr (gimple_cond_rhs (stmt)); + if (rhs == NULL_TREE) + return; + + if (TREE_CODE (lhs) == MINUS_EXPR && integer_zerop (rhs)) + { + /* Case 1: (x - y) CMP 0 */ + tree x = TREE_OPERAND (lhs, 0); + tree y = TREE_OPERAND (lhs, 1); + + /* => x CMP y */ + gimple_cond_set_lhs (stmt, x); + gimple_cond_set_rhs (stmt, y); + update_stmt (stmt); + } + else if (integer_zerop (lhs) && TREE_CODE (rhs) == MINUS_EXPR) + { + /* Case 2: 0 CMP (x - y) */ + tree x = TREE_OPERAND (rhs, 0); + tree y = TREE_OPERAND (rhs, 1); + + /* => y CMP x */ + gimple_cond_set_lhs (stmt, y); + gimple_cond_set_rhs (stmt, x); + update_stmt (stmt); + } +} + +/* Find signed integer comparisons where the operands are MINUS_EXPR and + 0, and replace them with the equivalent comparison of the operands of + the MINUS_EXPR without the subtraction. */ + +namespace { + +const pass_data pass_data_cmp = +{ + GIMPLE_PASS, /* type */ + "cmp", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_CMP, /* tv_id */ + PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_remove_unused_locals, /* todo_flags_finish */ +}; + +class pass_cmp : public gimple_opt_pass +{ +public: + pass_cmp (gcc::context *ctxt) + : gimple_opt_pass (pass_data_cmp, ctxt) + {} + + /* opt_pass methods: */ + bool gate (function *) final override + { + /* If -fwrapv is enabled, this pass cannot be safely applied as described + in the comment at the top of this file. */ + return flag_tree_cmp != 0 && flag_wrapv == 0; + } + + unsigned int execute (function *) final override; + +}; // class pass_cmp + +class cmp_dom_walker : public dom_walker +{ +public: + cmp_dom_walker () : dom_walker (CDI_DOMINATORS) {} + + void after_dom_children (basic_block) final override; +}; + +void +cmp_dom_walker::after_dom_children (basic_block bb) +{ + gimple_stmt_iterator gsi; + + for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (gimple_code (stmt) == GIMPLE_COND) + optimize_signed_comparison (as_a (stmt)); + } +} + + +unsigned int +pass_cmp::execute (function *) +{ + calculate_dominance_info (CDI_DOMINATORS); + cmp_dom_walker ().walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + return 0; +} + +} // anon namespace + +gimple_opt_pass * +make_pass_cmp (gcc::context *ctxt) +{ + return new pass_cmp (ctxt); +}