From patchwork Thu Jan 6 10:35:55 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhao Wei Liew X-Patchwork-Id: 49618 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8A641385800C for ; Thu, 6 Jan 2022 10:37:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8A641385800C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1641465421; bh=78B3UvuYB961AWi8FTrgVhmSI8cS+vcYDk1DtV288Qg=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=F+/HKoIxMsLVVJ6QmE2i4MUgKjvMf28LLZzfeyz+oYGBD3bPebSnCG2WNDSvAWqIf rfnjOU6eI8re52kSnMK7Fcslrol4sR0a7euDeojpAogvz/llwLAOnLvoJ5s5jLFpoi 57EwycttHq2kNXNXagYFD/NxPdEcBjpA5ixf6KAQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-io1-xd35.google.com (mail-io1-xd35.google.com [IPv6:2607:f8b0:4864:20::d35]) by sourceware.org (Postfix) with ESMTPS id 09E60385800C for ; Thu, 6 Jan 2022 10:36:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 09E60385800C Received: by mail-io1-xd35.google.com with SMTP id u8so2512678iol.5 for ; Thu, 06 Jan 2022 02:36:32 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc; bh=eziqaUDph7GHAK4Dy+NlOTVAlncU5eTf2+IHjxcZ3vY=; b=zXCzXC6sQQBGLV0x/mr6bxm1vax69rAfqEik0N1rGnocOS+c1tyCf6cUbHCs1REHjV 2xVHMImhwK0gqLe6CH0Y1N5MvxtXZwENU/fmutbhUVOvHbFcx7aXvz/O8ABjEDueyMDq RgE8I5vKsXlCgyvUFonczdP4RFF3syYuicuNO+2ouR5DiAxA9psTWo0IKOLK/1NpBOyu R6cWYvcH+G6Qf8H/xJv2p6S3EDD/uFh/ZDvn0CkH9MgjmK1cFSt/rlWPnzabMFZsgJSH Ixa4g/vjZpeF4WrMoL6srXyhB/Ksnu8l0wvm5R0ZB5U6MQgHmvU3iZQilR6GXvNSoWrI I2+Q== X-Gm-Message-State: AOAM530oRKt8lfYK8YEOUGCfUhV9O1Uz5RSwEndNMhWQ2swwREHlgESd BRCtP9vBkejC/WxjhWJwGQajFvEk7ak/fDP7rARWHFltQY77MFEKNRw= X-Google-Smtp-Source: ABdhPJywaFXmdv9Yxurym4sec9EJVi+fG7KjQwduF50YnmeqyFMaif5+Z5W0RTpeX4AdELiW6e8xkhRNmVjj2npY5B4= X-Received: by 2002:a5d:888c:: with SMTP id d12mr25993306ioo.175.1641465391144; Thu, 06 Jan 2022 02:36:31 -0800 (PST) MIME-Version: 1.0 Date: Thu, 6 Jan 2022 18:35:55 +0800 Message-ID: Subject: [PATCH v2] match.pd: Simplify 1 / X for integer X [PR95424] To: GCC Patches X-Spam-Status: No, score=-7.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, HTML_MESSAGE, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Zhao Wei Liew via Gcc-patches From: Zhao Wei Liew Reply-To: Zhao Wei Liew Cc: Jakub Jelinek Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" This patch implements an optimization for the following C++ code: int f(int x) { return 1 / x; } int f(unsigned int x) { return 1 / x; } Before this patch, x86-64 gcc -std=c++20 -O3 produces the following assembly: f(int): xor edx, edx mov eax, 1 idiv edi ret f(unsigned int): xor edx, edx mov eax, 1 div edi ret In comparison, clang++ -std=c++20 -O3 produces the following assembly: f(int): lea ecx, [rdi + 1] xor eax, eax cmp ecx, 3 cmovb eax, edi ret f(unsigned int): xor eax, eax cmp edi, 1 sete al ret Clang's output is more efficient as it avoids expensive div operations. With this patch, GCC now produces the following assembly: f(int): lea eax, [rdi + 1] cmp eax, 2 mov eax, 0 cmovbe eax, edi ret f(unsigned int): xor eax, eax cmp edi, 1 sete al ret which is virtually identical to Clang's assembly output. Any slight differences in the output for f(int) is possibly related to a different missed optimization. v1: https://gcc.gnu.org/pipermail/gcc-patches/2022-January/587634.html Changes from v1: 1. Refactor common if conditions. 2. Use build_[minus_]one_cst (type) to get -1/1 of the correct type. 3. Match only for TRUNC_DIV_EXPR and TYPE_PRECISION (type) > 1. gcc/ChangeLog: * match.pd: Simplify 1 / X where X is an integer. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/divide-6.c: New test. * gcc.dg/tree-ssa/divide-7.c: New test. --- gcc/match.pd | 15 +++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/divide-6.c | 9 +++++++++ gcc/testsuite/gcc.dg/tree-ssa/divide-7.c | 9 +++++++++ 3 files changed, 33 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/divide-6.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/divide-7.c diff --git a/gcc/match.pd b/gcc/match.pd index 84c9b918041..52a0f77f455 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -432,6 +432,21 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) && TYPE_UNSIGNED (type)) (trunc_div @0 @1))) + /* 1 / X -> X == 1 for unsigned integer X. + 1 / X -> X >= -1 && X <= 1 ? X : 0 for signed integer X. + But not for 1 / 0 so that we can get proper warnings and errors, + and not for 1-bit integers as they are edge cases better handled elsewhere. */ +(simplify + (trunc_div integer_onep@0 @1) + (if (INTEGRAL_TYPE_P (type) && !integer_zerop (@1) && TYPE_PRECISION (type) > 1) + (switch + (if (TYPE_UNSIGNED (type)) + (eq @1 { build_one_cst (type); })) + (if (!TYPE_UNSIGNED (type)) + (with { tree utype = unsigned_type_for (type); } + (cond (le (plus (convert:utype @1) { build_one_cst (utype); }) { build_int_cst (utype, 2); }) + @1 { build_zero_cst (type); })))))) + /* Combine two successive divisions. Note that combining ceil_div and floor_div is trickier and combining round_div even more so. */ (for div (trunc_div exact_div) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/divide-6.c b/gcc/testsuite/gcc.dg/tree-ssa/divide-6.c new file mode 100644 index 00000000000..a9fc4c04058 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/divide-6.c @@ -0,0 +1,9 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-optimized" } */ + +unsigned int f(unsigned int x) { + return 1 / x; +} + +/* { dg-final { scan-tree-dump-not "1 / x_..D.;" "optimized" } } */ +/* { dg-final { scan-tree-dump "x_..D. == 1;" "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/divide-7.c b/gcc/testsuite/gcc.dg/tree-ssa/divide-7.c new file mode 100644 index 00000000000..285279af7c2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/divide-7.c @@ -0,0 +1,9 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-optimized" } */ + +int f(int x) { + return 1 / x; +} + +/* { dg-final { scan-tree-dump-not "1 / x_..D.;" "optimized" } } */ +/* { dg-final { scan-tree-dump ".. <= 2 ? x_..D. : 0;" "optimized" } } */