From patchwork Sat Jan 28 01:04:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 49763 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:eb09:0:0:0:0:0 with SMTP id s9csp1128780wrn; Fri, 27 Jan 2023 17:05:49 -0800 (PST) X-Google-Smtp-Source: AK7set9D6ZHQnwHkSgSmzW6immlfYrntsShW1zzFHAGRlRqpElvy2UVr8iaYUm/j9AIOLieHOovW X-Received: by 2002:a17:906:b310:b0:878:52cd:9006 with SMTP id n16-20020a170906b31000b0087852cd9006mr9196139ejz.69.1674867949598; Fri, 27 Jan 2023 17:05:49 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1674867949; cv=none; d=google.com; s=arc-20160816; b=tJ9Jb4Ysvd290uRqbcI0vBYc9MSTL2p/Eo17oGR1cC10Kyqjy8vRvbqKl4ZjaKPOnR wgScu+2KHFvJCstRlmmAjVdKe26a/Sk/oYijjzGgKSkl8wIAsrrJ+onVgd5TtcG+ZYbS WX992fTQknTP6yLRNWqWTFXhJBoVE3tF4ASfPEb2yQJylET2nA4PV5mSIwA2LTvg4RcJ Vp2JSIVlCcNEDE2ZOE1rvLPegPqZWsn4pipCkKhzMQxIx6xNp+gIUoivQQAZRVjCvXIL zeN5yV5nrmm7tEs1tA5XghseHr9mRAzuvaKKLbibLXwb/eMYF5G0AiI7XedntUx55aCM +sjQ== 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=qDAOtKsXlQL7Ii4yYL/J8ttQ5F8xpyOaj1JNAQmHFMk=; b=o8Y8MxSXzW3YV2PRbsl7kTW7HqZb4ZcL8TUurgi5oevGckS4tH4Bs5XoY3bFZ3bJ0r kgUsOzUjaV6HAyRh7yl9gLPcWiRqxFQXAILGYubXkEjCH3gjoZDtB+WxtRqQ9HP8xvJr mzuUfUAAmfVhb85zymUmVRCL2pHB60ayIdCco8z7nqBD/1mL2wwLq7w6uD5OlsMN6XIN F/K561tjQv8DVwFN2657VVYFyx2J0Nu2myuECiLk6AMtm+EyiuGplw6P3V/iKLJ3g8Y/ OGrwiX4RmnkSK4qskQgUxLlPtllCIqv/HlSfhtNr5oQaH1bAzfPDbDz5S4j+QGilHulI gu7g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="h/8qMVjc"; 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 cp22-20020a17090793d600b008706eec02c0si6705145ejc.293.2023.01.27.17.05.49 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 27 Jan 2023 17:05:49 -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="h/8qMVjc"; 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 3BD99385B507 for ; Sat, 28 Jan 2023 01:05:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3BD99385B507 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1674867941; bh=qDAOtKsXlQL7Ii4yYL/J8ttQ5F8xpyOaj1JNAQmHFMk=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=h/8qMVjcmVGTI48s80CqHOssfiUVZbwR2AucE0+KSH8rRqWglOGy9QEubY/vSasV8 EU08Gz49uUDPt8EBMkdFKB8UEWoJq3ad01gQj/cgpmXsb4eQSWc+0M4DOeIYw7NTv4 k+UmHwK8rL0oFL5ORmeXgWsbMXnskqqdUXdtA8Rg= 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.129.124]) by sourceware.org (Postfix) with ESMTPS id 8B5773858D20 for ; Sat, 28 Jan 2023 01:04:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8B5773858D20 Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-99-ro4Uy1ZQMLOC7gxVmFELOg-1; Fri, 27 Jan 2023 20:04:47 -0500 X-MC-Unique: ro4Uy1ZQMLOC7gxVmFELOg-1 Received: by mail-qt1-f199.google.com with SMTP id ga12-20020a05622a590c00b003b62b38e077so2938030qtb.7 for ; Fri, 27 Jan 2023 17:04:47 -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=+NeFPxwxRB6TbpYZfHALBQUwPdORuOIfdELisbgrmLY=; b=xOuAKtPulcsRSrCP8iidEd/jTfW+aTOtSV5PI47UJTcWwe2oX9KfIuuYxeWhSFGchw qFwSdLjG/ZI+uDlGULscesGjfEN967hlCW6K0eABn8m0rlfxFqczTZM72ei46sLiT7zW BsQ8qRAmVVUi6hLdSNPWvbElysYxbAHk/9LkDJkYxHdoxhjYCQKSikSoD8tsjNFV8lDW eMCjQXV15pnz4wRaEn529nO2E/lHe5CGJ4Udd27swOZ9jRvVKwkql3lSADzy23l3dF+i 3uZEf8rJHWFFHClL60YsJO9xeXMDSexgVXqUPfQzTCEWR1Z4Kv/PQOwFgiNooS2ocuMF MJOg== X-Gm-Message-State: AO0yUKX+wF+78fSrms2LByLliDGP+Iwj1tAEv6FqGJjDwI3AEhMxNQPt kKhmYjKDHsoRFz9E6GsMXYN76euIOfJUqS1SDJUvHmGuSzP/FOQ0nQcXD4NlrD3ULRwNcy+EFwc eXHwI3bVVTCZyfvFJvurCN3JhJO0APeUuQikP14qwNTn8Ta2Gm8ns06qVraaI+xX4WL4HFg== X-Received: by 2002:a05:6214:5684:b0:537:7440:7586 with SMTP id lm4-20020a056214568400b0053774407586mr18221158qvb.0.1674867886872; Fri, 27 Jan 2023 17:04:46 -0800 (PST) X-Received: by 2002:a05:6214:5684:b0:537:7440:7586 with SMTP id lm4-20020a056214568400b0053774407586mr18221119qvb.0.1674867886417; Fri, 27 Jan 2023 17:04:46 -0800 (PST) Received: from ?IPV6:2607:fea8:a263:f600::fa90? ([2607:fea8:a263:f600::fa90]) by smtp.gmail.com with ESMTPSA id e8-20020a05620a12c800b006fa22f0494bsm3886012qkl.117.2023.01.27.17.04.45 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 27 Jan 2023 17:04:45 -0800 (PST) Message-ID: <79c78a5a-f2ec-7a1e-c3d6-d7091a2b4540@redhat.com> Date: Fri, 27 Jan 2023 20:04:44 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.6.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [PATCH 1/3] Properly set GORI relation trios. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.9 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?1756226335336829694?= X-GMAIL-MSGID: =?utf-8?q?1756226335336829694?= We added the concept of a relation trio this release.  Basically its a group of relations for a range-op statement indicating the relation between LHS & OP1, LHS & OP2, and OP1 & OP2. This is primarily used in GORI so we can use relations during range calculation on outgoing edges, although It is also use during folding. We currently use them in just a couple of places so it was not really fleshed out completely. The next couple of PRs require relations in range-ops, and in working with them, I found I had not been complete when I implemented relation_trio... just did enough to get it to work. This patch properly sets each of the fields in relation trio, and then queries the proper field in the couple of places that currently use it.  This patch invokes no new behaviour, just sets up the information correctly so future queries can get the right info.  It consolidates the relation trio setting code into one place (more utilization of the primary value_relation class) and is just basic goodness. It also allows the next 2 PRs to be fixed with minimal changes. Bootstraps on x86_64-pc-linux-gnu with no regressions. OK for trunk? Andrew From 5b552dde4d597444d867308fb94b9b49fac42927 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 25 Jan 2023 16:26:39 -0500 Subject: [PATCH 1/4] Properly set GORI relation trios. When relation trios were added to GORI, there was only one use. As they are utilized more by range-ops, it is apparent that the implelemtation was not complete. This patch fleshes it out completely so that every GORI operation has a complete relation trio. * gimple-range-gori.cc (gori_compute::compute_operand_range): Do not abort calculations if there is a valid relation available. (gori_compute::refine_using_relation): Pass correct relation trio. (gori_compute::compute_operand1_range): Create trio and use it. (gori_compute::compute_operand2_range): Ditto. * range-op.cc (operator_plus::op1_range): Use correct trio member. (operator_minus::op1_range): Use correct trio member. * value-relation.cc (value_relation::create_trio): New. * value-relation.h (value_relation::create_trio): New prototype. --- gcc/gimple-range-gori.cc | 70 ++++++++++++++-------------------------- gcc/range-op.cc | 4 +-- gcc/value-relation.cc | 34 +++++++++++++++++++ gcc/value-relation.h | 1 + 4 files changed, 62 insertions(+), 47 deletions(-) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 930e2a0f0ab..3dc4576ff13 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -632,6 +632,9 @@ gori_compute::compute_operand_range (vrange &r, gimple *stmt, if (op1 && op2) { relation_kind k = handler.op1_op2_relation (lhs); + // If there is no relation, and op1 == op2, create a relation. + if (!vrel_ptr && k == VREL_VARYING && op1 == op2) + k = VREL_EQ; if (k != VREL_VARYING) { vrel.set_relation (k, op1, op2); @@ -952,7 +955,9 @@ gori_compute::refine_using_relation (tree op1, vrange &op1_range, { gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); - gcc_checking_assert (k != VREL_VARYING && k != VREL_UNDEFINED); + + if (k == VREL_VARYING || k == VREL_EQ || k == VREL_UNDEFINED) + return false; bool change = false; bool op1_def_p = in_chain_p (op2, op1); @@ -991,7 +996,7 @@ gori_compute::refine_using_relation (tree op1, vrange &op1_range, Value_Range new_result (type); if (!op_handler.op1_range (new_result, type, op1_def_p ? op1_range : op2_range, - other_op, relation_trio::lhs_op2 (k))) + other_op, relation_trio::lhs_op1 (k))) return false; if (op1_def_p) { @@ -1023,7 +1028,7 @@ gori_compute::refine_using_relation (tree op1, vrange &op1_range, Value_Range new_result (type); if (!op_handler.op2_range (new_result, type, op1_def_p ? op1_range : op2_range, - other_op, relation_trio::lhs_op1 (k))) + other_op, relation_trio::lhs_op2 (k))) return false; if (op1_def_p) { @@ -1062,6 +1067,10 @@ gori_compute::compute_operand1_range (vrange &r, tree op2 = handler.operand2 (); tree lhs_name = gimple_get_lhs (stmt); + relation_trio trio; + if (rel) + trio = rel->create_trio (lhs_name, op1, op2); + Value_Range op1_range (TREE_TYPE (op1)); Value_Range tmp (TREE_TYPE (op1)); Value_Range op2_range (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1)); @@ -1073,27 +1082,11 @@ gori_compute::compute_operand1_range (vrange &r, if (op2) { src.get_operand (op2_range, op2); - relation_kind k = VREL_VARYING; - relation_kind op_op = (op1 == op2) ? VREL_EQ : VREL_VARYING; - if (rel) - { - if (lhs_name == rel->op1 () && op1 == rel->op2 ()) - k = rel->kind (); - else if (lhs_name == rel->op2 () && op1 == rel->op1 ()) - k = relation_swap (rel->kind ()); - else if (op1 == rel->op1 () && op2 == rel->op2 ()) - { - op_op = rel->kind (); - refine_using_relation (op1, op1_range, op2, op2_range, src, op_op); - } - else if (op1 == rel->op2 () && op2 == rel->op1 ()) - { - op_op = relation_swap (rel->kind ()); - refine_using_relation (op1, op1_range, op2, op2_range, src, op_op); - } - } - if (!handler.calc_op1 (tmp, lhs, op2_range, relation_trio (VREL_VARYING, - k, op_op))) + relation_kind op_op = trio.op1_op2 (); + if (op_op != VREL_VARYING) + refine_using_relation (op1, op1_range, op2, op2_range, src, op_op); + + if (!handler.calc_op1 (tmp, lhs, op2_range, trio)) return false; } else @@ -1101,7 +1094,7 @@ gori_compute::compute_operand1_range (vrange &r, // We pass op1_range to the unary operation. Nomally it's a // hidden range_for_type parameter, but sometimes having the // actual range can result in better information. - if (!handler.calc_op1 (tmp, lhs, op1_range, TRIO_VARYING)) + if (!handler.calc_op1 (tmp, lhs, op1_range, trio)) return false; } @@ -1172,29 +1165,16 @@ gori_compute::compute_operand2_range (vrange &r, src.get_operand (op1_range, op1); src.get_operand (op2_range, op2); - relation_kind k = VREL_VARYING; - relation_kind op_op = (op1 == op2) ? VREL_EQ : VREL_VARYING; + + relation_trio trio; if (rel) - { - if (lhs_name == rel->op1 () && op2 == rel->op2 ()) - k = rel->kind (); - else if (lhs_name == rel->op2 () && op2 == rel->op1 ()) - k = relation_swap (rel->kind ()); - else if (op1 == rel->op1 () && op2 == rel->op2 ()) - { - op_op = rel->kind (); - refine_using_relation (op1, op1_range, op2, op2_range, src, op_op); - } - else if (op1 == rel->op2 () && op2 == rel->op1 ()) - { - op_op = relation_swap (rel->kind ()); - refine_using_relation (op1, op1_range, op2, op2_range, src, op_op); - } - } + trio = rel->create_trio (lhs_name, op1, op2); + relation_kind op_op = trio.op1_op2 (); + if (op_op != VREL_VARYING) + refine_using_relation (op1, op1_range, op2, op2_range, src, op_op); // Intersect with range for op2 based on lhs and op1. - if (!handler.calc_op2 (tmp, lhs, op1_range, relation_trio (k, VREL_VARYING, - op_op))) + if (!handler.calc_op2 (tmp, lhs, op1_range, trio)) return false; unsigned idx; diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 6e5754e9130..ed2dd1eb99c 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -1460,7 +1460,7 @@ operator_plus::op1_range (irange &r, tree type, if (!minus) return false; bool res = minus.fold_range (r, type, lhs, op2); - relation_kind rel = trio.lhs_op2 (); + relation_kind rel = trio.lhs_op1 (); // Check for a relation refinement. if (res) adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */); @@ -1632,7 +1632,7 @@ operator_minus::op1_range (irange &r, tree type, if (!minus) return false; bool res = minus.fold_range (r, type, lhs, op2); - relation_kind rel = trio.lhs_op2 (); + relation_kind rel = trio.lhs_op1 (); if (res) adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */); return res; diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 5ca8a7eb0d9..f5b1e67e420 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -883,6 +883,40 @@ value_relation::apply_transitive (const value_relation &rel) return false; } +// Create a trio from this value relation given LHS, OP1 and OP2. + +relation_trio +value_relation::create_trio (tree lhs, tree op1, tree op2) +{ + relation_kind lhs_1; + if (lhs == name1 && op1 == name2) + lhs_1 = related; + else if (lhs == name2 && op1 == name1) + lhs_1 = relation_swap (related); + else + lhs_1 = VREL_VARYING; + + relation_kind lhs_2; + if (lhs == name1 && op2 == name2) + lhs_2 = related; + else if (lhs == name2 && op2 == name1) + lhs_2 = relation_swap (related); + else + lhs_2 = VREL_VARYING; + + relation_kind op_op; + if (op1 == name1 && op2 == name2) + op_op = related; + else if (op1 == name2 && op2 == name1) + op_op = relation_swap (related); + else if (op1 == op2) + op_op = VREL_EQ; + else + op_op = VREL_VARYING; + + return relation_trio (lhs_1, lhs_2, op_op); +} + // Dump the relation to file F. void diff --git a/gcc/value-relation.h b/gcc/value-relation.h index 664fd71c925..340f9c42554 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -426,6 +426,7 @@ public: inline tree op1 () const { return name1; } inline tree op2 () const { return name2; } + relation_trio create_trio (tree lhs, tree op1, tree op2); bool union_ (value_relation &p); bool intersect (value_relation &p); void negate (); -- 2.39.0 From patchwork Sat Jan 28 01:04:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 49764 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:eb09:0:0:0:0:0 with SMTP id s9csp1128803wrn; Fri, 27 Jan 2023 17:05:53 -0800 (PST) X-Google-Smtp-Source: AK7set83i4getYBJjUM8fB0KpXOsiAc6U+eiwrBF3zA1iVdKgl4LM34CSDs7+wgOtRSqNaGlA7On X-Received: by 2002:aa7:d4cf:0:b0:4a2:1263:bbab with SMTP id t15-20020aa7d4cf000000b004a21263bbabmr3663787edr.17.1674867953272; Fri, 27 Jan 2023 17:05:53 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1674867953; cv=none; d=google.com; s=arc-20160816; b=rWsV6YvKoauWuaJXPUbeb9jxKNKMmZJG/TJqcg2eW4CFaYsqqm1taArxrtYqMx+xmR flQvI6vs4dXrMbrjujPt+6A2u581Y+LcFIMXfu8jRi1v/VPhpaWDCgdmhgC0zmvJykuN F681LzYs1w6vTSuJuak5xK4fj5rHS6s+Opv4c0Ip7Gz0sQgH11pDvOoth7H1zwUFEgu/ 5js3AyUaIGpyE0Xb3DXtxagsztQFMkZP0fBEgH7Rr7rrQzemO9JSpTloOwP7BzgR4vs7 NqeynBXJD6DmZaudmBKk+7+x7p/xGOYqIItsNqBuTe0jgBCuz7CjQ2NA4Nkev3+lv1yo Ei/A== 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=O9/BU5c0SOrRHns0NzS3RnZ0g9vxAjqwsxSGTHy9KN4=; b=pNPUJupwVrPysvvjTyAAAqehPKSvw7CPZ+5rPf9xrvn1u/aN019K38DLzT8EljawHY cuSZK8atvt9iHPNVYKcYkWKsLgBr1cw32nfQ6DcKeEQfD1IPOJbnVDrwzl7yUs02owOE 1zqmnOBRsQGe7Wk2Uls1bB4/XqnHtVua8wkrbWBGQ/4HA7JTnENWpmGNUEALddnaMKGp 7SUplv+HHP4abbCdQVrTu0Bw71edp9s3IGpj812mJctTn62xKb7/pDkoD3x65YIGebzT 2eUJJSC9qkjGMt1QaR26cLuwYEv6c6xpFr5Rs3TythgSE98p4KSlWH4xc0dVGjsZnTBT p2Kw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=nnp6Xbo6; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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. [8.43.85.97]) by mx.google.com with ESMTPS id d13-20020a50ea8d000000b0049ec3a108d2si6718570edo.18.2023.01.27.17.05.53 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 27 Jan 2023 17:05:53 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=nnp6Xbo6; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 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 898893858433 for ; Sat, 28 Jan 2023 01:05:44 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 898893858433 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1674867944; bh=O9/BU5c0SOrRHns0NzS3RnZ0g9vxAjqwsxSGTHy9KN4=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=nnp6Xbo6C+P5sudrqEczOq/+OLso9N2EkW535eB+gH1kQZSVh2RaAIYeLWUqekdOr johtbqaPbbGRxI+TWVKseJkgIr5aFduAAIRS0SsPU7dW95VpZP7rM+a+/Zj5vpjV2R TWvG/Jvz6CpenHd16Vr8Nyk906kh8zX7vjpVCi8Q= 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.129.124]) by sourceware.org (Postfix) with ESMTPS id 658BC3858C54 for ; Sat, 28 Jan 2023 01:04:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 658BC3858C54 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-643-RDkHCobjONusLca2tiwKsA-1; Fri, 27 Jan 2023 20:04:53 -0500 X-MC-Unique: RDkHCobjONusLca2tiwKsA-1 Received: by mail-qv1-f72.google.com with SMTP id lp6-20020a056214590600b0053a07384c95so397584qvb.4 for ; Fri, 27 Jan 2023 17:04:53 -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=l19Vz5csF6IDuH90rRYnNFHO+BB1gJwc4UTY0GQA3f8=; b=ZD9c1HyQb1Z0MCP3o7BeF7KD7laR5Z8KQf6g4G36ULlovPlVBIcy5F7IW1JdaT/NEV v+OthzkCS3ZyQT3qN1fDoH3bQvh2drRP51X2lQB1tLLyonYNri4A68EnVMt5Cdy7k3kZ 6NcdGUI4TKTIcukW/OR+1G3t2ev+crt6LJXYnyRbAToiThUYyi+S5Ih6nPtczN3uvDNi 6alVf6Jo9sbm+4FAyk8CPuHM7NHgZpxq0grk2lA1EX7bxVcnhGjv8Ip9zHudI9/bWT+K yoox4c+NsQcaF1BWuKfI+NU7p9pLiGSYJ7CRPZW15SpiK1HmgdmOJ69xt8pW4dx4aWWC kUUw== X-Gm-Message-State: AFqh2kq+AnKTEVP3fIrl3oqZA6XsiqPuc6jr/8Cg60u2k8ux6QGusWnT cvAHANb4kHsIxb9++rpw/nuCu9RTsUFSA9sbYfFthGLW6EjmQI+XGYL1Wxn1YFDeXkSbzmjQKPD 2K/Mwu5xOjlNpd6YjU7a6TtRGt4olEdRTxxyPbPQbFcndm/s9YzOPIQ+UMa60pUNT8kTPoQ== X-Received: by 2002:a0c:bed2:0:b0:534:26eb:a25d with SMTP id f18-20020a0cbed2000000b0053426eba25dmr57982848qvj.40.1674867892583; Fri, 27 Jan 2023 17:04:52 -0800 (PST) X-Received: by 2002:a0c:bed2:0:b0:534:26eb:a25d with SMTP id f18-20020a0cbed2000000b0053426eba25dmr57982828qvj.40.1674867892259; Fri, 27 Jan 2023 17:04:52 -0800 (PST) Received: from ?IPV6:2607:fea8:a263:f600::fa90? ([2607:fea8:a263:f600::fa90]) by smtp.gmail.com with ESMTPSA id eb10-20020a05620a480a00b007112aa42c4fsm3774398qkb.135.2023.01.27.17.04.51 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 27 Jan 2023 17:04:51 -0800 (PST) Message-ID: Date: Fri, 27 Jan 2023 20:04:50 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.6.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [PATCH 2/3] PR tree-optimization/108359 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_NUMSUBJECT, 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?1756226338942341442?= X-GMAIL-MSGID: =?utf-8?q?1756226338942341442?= If there exists an equivalence relationship between op1 and op2,any binary operation can be broken into individual operations and unioned if there are sufficiently few elements in the set. This depends on the first patch as we need to get the relation op1 == op2 correct in to the relation_trio set. There were various suggestions on how to "control" when we perform the sub-folds and when we continue using the aggregate. I settled on passing into wi_fold_in_parts_equiv a limit, which is currently either 0 or 8.  As long as there are 8 or less ranges n the subrange, we split it up, until the range we are accumulating into reaches 32 subranges... then we just do aggregates again. That should allow us to do a "good job" for a while, but bail before it becomes wasteful. Bootstraps on x86_64-pc-linux-gnu with no regressions,  OK for trunk? (3rd patch is delayed while I look into it further) Andrew From 409fc68cd85953c77e02588057a9eb0d21991475 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 17 Jan 2023 11:14:41 -0500 Subject: [PATCH 2/4] 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 | 54 +++++++++++++++++++++++++++++++++ gcc/range-op.h | 6 ++++ gcc/testsuite/gcc.dg/pr108359.c | 52 +++++++++++++++++++++++++++++++ 3 files changed, 112 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/pr108359.c diff --git a/gcc/range-op.cc b/gcc/range-op.cc index ed2dd1eb99c..f7c1e84e0bd 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -160,6 +160,38 @@ 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] +// LIMIT is the maximum number of elements in range allowed before we +// do not processs them individually. + +void +range_operator::wi_fold_in_parts_equiv (irange &r, tree type, + const wide_int &lh_lb, + const wide_int &lh_ub, + unsigned limit) 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 < limit) + { + for (unsigned 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 +266,28 @@ 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) + { + // If the number of subranges is too high, limit subrange creation. + unsigned limit = (r.num_pairs () > 32) ? 0 : 8; + 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, limit); + 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..f00b747f08a 100644 --- a/gcc/range-op.h +++ b/gcc/range-op.h @@ -109,6 +109,12 @@ 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, + unsigned limit) 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..7cf04f74132 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr108359.c @@ -0,0 +1,52 @@ +/* { 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 + This function should never call foo (). */ + +int otherfunc (int x, int z) { + if (x < 1 || x > 6 ) + return 0; + + if (x == z) + { + if (x >> z > 0) + foo (); + if (x * z > 26 && x * z < 35) + foo (); + if (x + z == 5) + foo (); + if ((x + z) % 2 == 1) + foo (); + if (x / z != 1) + foo (); + + } + return 0; +} + + +/* { dg-final { scan-tree-dump-not "foo" "optimized" } } */ -- 2.39.0