From patchwork Fri Jan 13 21:23:20 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 43616 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp488338wrt; Fri, 13 Jan 2023 13:24:29 -0800 (PST) X-Google-Smtp-Source: AMrXdXtS2b3yP3jd/KCLwTbwSzlskhsO4KCwk3ph8jAxla54EM37yWJgx+1w3IVDnlViNyfvASlP X-Received: by 2002:a17:906:5db2:b0:7c0:8c83:79b8 with SMTP id n18-20020a1709065db200b007c08c8379b8mr5150175ejv.53.1673645069144; Fri, 13 Jan 2023 13:24:29 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673645069; cv=none; d=google.com; s=arc-20160816; b=z+3uZZZsXQv9lePNuXBsl+VC/UKx/ozDGA8dM129UhUYxg2RYhCwfVyHsuD7exPutT K5hH723R+yWWdmE77CbZ3fFZvjWKAvVjhN1QDEPESEzOWticlk5nfM2oYWlbTfo5MyEl 3t0FYdZpRAUbaV5hEI1Qk3Ck0NpbB7eAAx8yQuP98X5UTSVGvQoPPuzUJQ0C0MzPpf0J b7K+DURkrm6d8+hBSuFrqLdj81aWHOwmfHMEWxK8pdZmvd3M2RQ16Zy0ocx6xfmz2+DX f/SSrnELzjC91bipDJJqXrkfXIYxvPd+bBMWU1OkUEHqKVmuwJkmCYfAYBq2cCozjiE1 6pBA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:content-language :subject:cc:to:user-agent:mime-version:date:message-id:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=1nxrbwKfDBJDuWERpnGIHE8KcG5RlzDscnoEHUO6zek=; b=DBgLHij0BzeqgfsDpcECyej+q97LR3H5EiAqXCsSDCZQNg1q8Xkm6O2F79tWIbBgUo YBggi5elyQtoovad/U+JDBKJWgu/LmhmjrC6v4MP3MkMUediAzxmbIRWYvsE0R8ddw1x WUvPHCu0cy3HetB6/WgMHq90w/H5cFVLQif58N1mMTfLIlh12fhFAer/u/p1X5dPZqhV oY6cXKl6eQIiGry8cYoPD1+dRVcDZsg7KJK6vMjjivZzeSeKxvaE6Yhh3CqvXW1hCGsU wyGJl9JqzRQARODRB4vLArF9jSUSbHvwLpqUrL+i/NTjRuB6xy04LB8DyevXttptRArm 4aZg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=p1cfR3V0; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id hg2-20020a1709072cc200b0084d4730001asi16606875ejc.89.2023.01.13.13.24.28 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 13 Jan 2023 13:24:29 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=p1cfR3V0; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id EA1DB384A019 for ; Fri, 13 Jan 2023 21:24:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org EA1DB384A019 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1673645068; bh=1nxrbwKfDBJDuWERpnGIHE8KcG5RlzDscnoEHUO6zek=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=p1cfR3V0ExZm6ZBUEuLkSfm1J2JlqH+C+IERaIJTuRKqh4ADo7+QNLhp6EkOJWrIY DO5y6Q++Sitj2EKtA7diOXHkH0+DdWJ8O3FoC69JDGt6XbwPjC68GRIVSNZ/Phe7F4 NGZt0dVsmZW1nj9FaJFf28qdqiygvJbBiYnE/SPY= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id D6E9F3858425 for ; Fri, 13 Jan 2023 21:23:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D6E9F3858425 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-646-SNwX7bpBNuK5J9sghU2ACw-1; Fri, 13 Jan 2023 16:23:28 -0500 X-MC-Unique: SNwX7bpBNuK5J9sghU2ACw-1 Received: by mail-qk1-f200.google.com with SMTP id bp6-20020a05620a458600b006ffd3762e78so16017458qkb.13 for ; Fri, 13 Jan 2023 13:23:28 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=qvIwjVQ05dDUEN1/plo7Ym3UauOReVSbNwGgPmoq/IQ=; b=5J8p+8/Xrsnf3WMYBXouocNmbCeigqjKzA6DS4EaJQ92xUOXECKouYFoteobT6u7HZ 627wOVcnhVtI3YwAtj85MmikoLJoxdxWAaxeuV/XbF6zKXIyS/PCX/uCEZJoGF7VOkzL /KYqiHK+EUbEqe4IhA5+3Vm3CpP/GEkzUuOQmBvexgiGi/0ou25RRI+ycCVDnlzo48tr B7IxT2fXDfALbZMZ6Qce9bY26zHZNIlBhuIrdz0GI21l2Y1n2gAtS7KGB9eIZRGLHF3m YK0rqGUkWhlII6kTaJ9rGAbKOZcTNlZU1T6siFQHRsbXySyJWKrmCPpOHC3vxjBHskoK jpHQ== X-Gm-Message-State: AFqh2kqxr2CjS5iS1prh+9bWKXn9BM2UFxHdE0rodKpWAsfPj7/LXkvu ZxQLFdgq8QE0y1X2VY8FSLb2rsw2aME9f7Mxbu4VdjDM7ttdvtVevX3c6rLQsvZCCxyDKVmZ7JY HU6wRw5i6LJEA7WJrzfQzXLVHuJKRqAyTDNQ9sI67g1RWfZyhAVSb3waKfVjvjk/16kLKoQ== X-Received: by 2002:a05:622a:124b:b0:3ab:7bb3:4707 with SMTP id z11-20020a05622a124b00b003ab7bb34707mr100252589qtx.64.1673645007917; Fri, 13 Jan 2023 13:23:27 -0800 (PST) X-Received: by 2002:a05:622a:124b:b0:3ab:7bb3:4707 with SMTP id z11-20020a05622a124b00b003ab7bb34707mr100252560qtx.64.1673645007502; Fri, 13 Jan 2023 13:23:27 -0800 (PST) Received: from ?IPV6:2607:fea8:a263:f600::27bf? ([2607:fea8:a263:f600::27bf]) by smtp.gmail.com with ESMTPSA id cr26-20020a05622a429a00b003a68fe872a5sm11007687qtb.96.2023.01.13.13.23.26 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 13 Jan 2023 13:23:26 -0800 (PST) Message-ID: <3815f4c2-7a8d-c662-54d8-eac1ab315fbb@redhat.com> Date: Fri, 13 Jan 2023 16:23:20 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.5.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [PATCH] PR tree-optimization/108359 - Utilize op1 == op2 when invoking range-ops folding. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1754944052118468002?= X-GMAIL-MSGID: =?utf-8?q?1754944052118468002?= fold_range() already invokes wi_fold_in_parts to try to get more refined information. If the subranges are quite small, it will do each individual calculation and combine the results. x * y with x = [1,3] and y = [1,3]  is broken down and we calculate each possibility and we end up with [1,4][6,6][9,9] instead of [1,9] We limit this as the time is between quadratic to exponential depending on the number of elements in x and y. If we also check the relation and determine that x == y, we don't need to worry about that growth as this process is linear.  The above case will be broken down to just  1*1, 2*2 and 3*3, resulting in a range of [1, 1][4,4][9,9].  In the testcase, it happens to be the right_shift operation, but this solution is generic and applies to all range-op operations. I added a testcase which checks >>, *, + and %. I also arbitrarily chose 8 elements as the limit for breaking down individual operations.  The overall compile time change for this is negligible. Although this is a regression fix, it will affect all operations where x == y, which is where my initial hesitancy arose. Regardless, bootstrapped on x86_64-pc-linux-gnu with no regressions.  OK for trunk? Andrew From fd50dabc626cea1886ebb517ca24c8b8f199c3aa Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 11 Jan 2023 18:12:51 -0500 Subject: [PATCH 2/3] Utilize op1 == op2 when invoking range-ops folding. If there exists an equivalence relationship between op1 and op2, any binary operation can be broken into individual operations and unioned if there are sufficently few elements in the set. PR tree-optimization/108359 gcc/ * range-op.cc (range_operator::wi_fold_in_parts_equiv): New. (range_operator::fold_range): If op1 is equivalent to op2 then invoke new fold_in_parts_equiv to operate on sub-components. * range-op.h (wi_fold_in_parts_equiv): New prototype. gcc/testsuite/ * gcc.dg/pr108359.c: New. --- gcc/range-op.cc | 50 +++++++++++++++++++++++++++++++++ gcc/range-op.h | 5 ++++ gcc/testsuite/gcc.dg/pr108359.c | 50 +++++++++++++++++++++++++++++++++ 3 files changed, 105 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/pr108359.c diff --git a/gcc/range-op.cc b/gcc/range-op.cc index ec75e07bc8a..2cb2c1344f1 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -160,6 +160,36 @@ range_operator::wi_fold (irange &r, tree type, r.set_varying (type); } +// Call wi_fold when both op1 and op2 are equivalent. Further split small +// subranges into constants. This can provide better precision. +// For x + y, when x == y with a range of [0,4] instead of [0, 8] produce +// [0,0][2, 2][4,4][6, 6][8, 8] + +void +range_operator::wi_fold_in_parts_equiv (irange &r, tree type, + const wide_int &lh_lb, + const wide_int &lh_ub) const +{ + int_range_max tmp; + widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)), + widest_int::from (lh_lb, TYPE_SIGN (type))); + // if there are 1 to 8 values in the LH range, split them up. + r.set_undefined (); + if (lh_range >= 0 && lh_range <= 7) + { + unsigned x; + for (x = 0; x <= lh_range; x++) + { + wide_int val = lh_lb + x; + wi_fold (tmp, type, val, val, val, val); + r.union_ (tmp); + } + } + // Otherwise just call wi_fold. + else + wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub); +} + // Call wi_fold, except further split small subranges into constants. // This can provide better precision. For something 8 >> [0,1] // Instead of [8, 16], we will produce [8,8][16,16] @@ -234,6 +264,26 @@ range_operator::fold_range (irange &r, tree type, unsigned num_lh = lh.num_pairs (); unsigned num_rh = rh.num_pairs (); + // If op1 and op2 are equivalences, then we don't need a complete cross + // product, just pairs of matching elements. + if (relation_equiv_p (rel) && (lh == rh)) + { + int_range_max tmp; + r.set_undefined (); + for (unsigned x = 0; x < num_lh; ++x) + { + wide_int lh_lb = lh.lower_bound (x); + wide_int lh_ub = lh.upper_bound (x); + wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub); + r.union_ (tmp); + if (r.varying_p ()) + break; + } + op1_op2_relation_effect (r, type, lh, rh, rel); + update_known_bitmask (r, m_code, lh, rh); + return true; + } + // If both ranges are single pairs, fold directly into the result range. // If the number of subranges grows too high, produce a summary result as the // loop becomes exponential with little benefit. See PR 103821. diff --git a/gcc/range-op.h b/gcc/range-op.h index b7b8a3b9473..998aeedb0d9 100644 --- a/gcc/range-op.h +++ b/gcc/range-op.h @@ -109,6 +109,11 @@ protected: const wide_int &rh_lb, const wide_int &rh_ub) const; + // Called by fold range to split small subranges into parts when op1 == op2 + void wi_fold_in_parts_equiv (irange &r, tree type, + const wide_int &lb, + const wide_int &ub) const; + // Tree code of the range operator or ERROR_MARK if unknown. tree_code m_code; }; diff --git a/gcc/testsuite/gcc.dg/pr108359.c b/gcc/testsuite/gcc.dg/pr108359.c new file mode 100644 index 00000000000..00fd2de6dc7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr108359.c @@ -0,0 +1,50 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* PR test case. */ +int b = 10; +int c; +char e; +void foo(); +static char(a)(char f, char g) { return f && g == 1 ? 0 : f % g; } +short(d)(short f, short g) { return f * g; } +int main() { + short h; + int i; + unsigned j; + h = d(b && c, 5); + j = h; + i = a(h, 237); + unsigned k = i; + e = i < 0 || k >= 32 ? 0 : i >> k; + if (e) { + c = 0; + foo(); + } +} + + +/* Also Check that small ranges are broken down and optimized properly + in the egneric case. This function should always return 0. */ + +int otherfunc (int x, int z) { + if (x < 0 || x > 6 ) + return 0; + + if (x == z) + { + if (x >> z > 0) + return 1; + if (x * z > 26 && x * z < 35) + return 1; + if (x + z == 5) + return 1; + if ((x + z) % 2 == 1) + return 1; + } + return 0; +} + + +/* { dg-final { scan-tree-dump-not "foo" "optimized" } } */ +/* { dg-final { scan-tree-dump-not "return 1" "optimized" } } */ -- 2.38.1