From patchwork Tue Feb 22 16:40:17 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1596256 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.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=lsHBRhb2; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from 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 RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4K34hz5pCWz9sG7 for ; Wed, 23 Feb 2022 03:42:43 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 37BEE3945C1A for ; Tue, 22 Feb 2022 16:42:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 37BEE3945C1A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1645548161; bh=5vaWMgJO6KSWYEOWhJHt2tU2o0v7u0zqFAVqC0WwYU4=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=lsHBRhb2QGBOhqpj1+3LGdoGQWHnXHE9lmN67QpWAFeLXYyrm+GsQYibI5xthxR/N skD/mX7+MxVvb3BMFeK8oeCRShpkOV02+x/EJbVIjo/4WDimqV+gwDCaKJrwUCEmQD XoDooW0USM9RkFOad0Styx5a03sBnaDXsOPheX6U= 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 21071382EB97 for ; Tue, 22 Feb 2022 16:40:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 21071382EB97 Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-140--TFlykSdN7aYxE62OVNKbQ-1; Tue, 22 Feb 2022 11:40:20 -0500 X-MC-Unique: -TFlykSdN7aYxE62OVNKbQ-1 Received: by mail-qk1-f199.google.com with SMTP id i189-20020a3786c6000000b00646d7b30998so134550qkd.10 for ; Tue, 22 Feb 2022 08:40:20 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:cc:from:subject; bh=wpZMpmKLdE+rDadNXcPXs2C/tKyTtQygxmkWXd3TdzY=; b=y0vjLiFgQII+WGUpB4xUGz4cqjo4LoXDsd1Hw/wzf+1MNMwV6iDbvU04rRgkMpPSbU 3t2hX2bALuwtZPF6NMhMLuYyESOhwnc8EDae155v6s55lldP3kVwUn4B3smU5meVLdls VxxZbf+urBgfcEQy9d56PB26EWIXk6DZ24DfvS/1/CU0JQFDfbGEit22B/rTVuM2xtBH kv1Y21kswYbHKWA/TZj3aySJJzG0279G69EHA4UnRAV3Zc8zsMLEgXyq6ZxYuZwJIhPR Fm0UiEBbGo/4s1FlaYiCHHn3VfuO/VTWzTxQ58ynRvccaCkvTQqO+IVamvgW7GaHcMN6 bX8A== X-Gm-Message-State: AOAM530+XPjrvREpVtqH6ma5oPU7ysqlckVxlS/QRchcxAEOdQzSmnEZ RPsKe+UiYByn8T0gk1u8ig0tie5YPFop3a3NHehi+VSLajior+vdqbS+1xl09442kxe9Ypyc9mE ZzEmetvriIK6jNvZXo8ZTpKdo4d/gE31SHRBvPKzs9l9RKbfFKU81e5GYFAu3ReVscm8sAQ== X-Received: by 2002:a37:688c:0:b0:507:db8b:b71a with SMTP id d134-20020a37688c000000b00507db8bb71amr15467084qkc.396.1645548019877; Tue, 22 Feb 2022 08:40:19 -0800 (PST) X-Google-Smtp-Source: ABdhPJxiF0ySVgbpx+8qsGYRjO/o/6PVvyXRbaO/geJj5N/+fvAgCtOOn3qz4SZuK8h1hyLqU7aKFA== X-Received: by 2002:a37:688c:0:b0:507:db8b:b71a with SMTP id d134-20020a37688c000000b00507db8bb71amr15467051qkc.396.1645548019484; Tue, 22 Feb 2022 08:40:19 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id d18sm45340qty.70.2022.02.22.08.40.18 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 22 Feb 2022 08:40:18 -0800 (PST) Message-ID: <16cb11c5-c46e-b0ae-2813-52f141414a41@redhat.com> Date: Tue, 22 Feb 2022 11:40:17 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.6.0 To: gcc-patches Subject: [PATCH 2/2] tree-optimization/104530 - Mark defs dependent on non-null stale. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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-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 Cc: Jakub Jelinek Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch simply leverages the existing computation machinery to re-evaluate values dependent on a newly found non-null value Ranger associates a monotonically increasing temporal value with every def as it is defined.  When that value is used, we check if any of the values used in the definition have been updated, making the current cached global value stale.  This makes the evaluation lazy, if there are no more uses, we will never re-evaluate. When an ssa-name is marked non-null it does not change the global value, and thus will not invalidate any global values.  This patch marks any definitions in the block which are dependent on the non-null value as stale.  This will cause them to be re-evaluated when they are next used. Imports: b.0_1  d.3_7 Exports: b.0_1  _2  _3  d.3_7  _8          _2 : b.0_1(I)          _3 : b.0_1(I)  _2          _8 : b.0_1(I)  _2  _3  d.3_7(I)    b.0_1 = b;     _2 = b.0_1 == 0B;     _3 = (int) _2;     c = _3;     _5 = *b.0_1;        <<-- from this point b.0_1 is [+1, +INF]     a = _5;     d.3_7 = d;     _8 = _3 % d.3_7;     if (_8 != 0) when _5 is defined, and n.0_1 becomes non-null,  we mark the dependent names that are exports and defined in this block as stale.  so _2, _3 and _8. When _8 is being calculated, _3 is stale, and causes it to be recomputed.  it is dependent on _2, alsdo stale, so it is also recomputed, and we end up with   _2 == [0, 0]   _3 == [0 ,0] and _8 = [0, 0] And then we can fold away the condition. The side effect is that _2 and _3 are globally changed to be [0, 0], but this is OK because it is the definition block, so it dominates all other uses of these names, and they should be [0,0] upon exit anyway.  The previous patch ensure that the global values written to SSA_NAME_RANGE_INFO is the correct [0,1] for both _2 and _3. The patch would have been even smaller if I already had a mark_stale method.   I thought there was one, but I guess it never made it in from lack of need at the time.   The only other tweak was to make the value stale if the dependent value was the same as the definitions. This bootstraps on x86_64-pc-linux-gnu with no regressions. Re-running to ensure. OK for trunk? or defer to stage 1? Andrew From a7e4e5f04899817cacc3ebe5cc3ff2d489489309 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 22 Feb 2022 09:58:00 -0500 Subject: [PATCH 2/2] Mark defs dependent on non-null stale. When a name is marked as non-null, find all exports from the block, and mark their timestamp as stale. Any following use of the name will trigger a recomputaion using the new non-null range. PR tree-optimization/104530 gcc/ * gimple-range-cache.cc (temporal_cache::set_stale): New. (temporal_cache::current_p): Identical timestamp is not current. (ranger_cache::update_to_nonnull): Mark any export defined in this block stale if it is dependent on this name. gcc/testsuite/ * gcc.dg/pr104530.c: New. --- gcc/gimple-range-cache.cc | 26 ++++++++++++++++++++++++-- gcc/testsuite/gcc.dg/pr104530.c | 17 +++++++++++++++++ 2 files changed, 41 insertions(+), 2 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr104530.c diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 613135266a4..debc93767a9 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -696,6 +696,7 @@ public: bool current_p (tree name, tree dep1, tree dep2) const; void set_timestamp (tree name); void set_always_current (tree name); + void set_stale (tree name); private: unsigned temporal_value (unsigned ssa) const; @@ -740,9 +741,9 @@ temporal_cache::current_p (tree name, tree dep1, tree dep2) const // Any non-registered dependencies will have a value of 0 and thus be older. // Return true if time is newer than either dependent. - if (dep1 && ts < temporal_value (SSA_NAME_VERSION (dep1))) + if (dep1 && ts <= temporal_value (SSA_NAME_VERSION (dep1))) return false; - if (dep2 && ts < temporal_value (SSA_NAME_VERSION (dep2))) + if (dep2 && ts <= temporal_value (SSA_NAME_VERSION (dep2))) return false; return true; @@ -759,6 +760,18 @@ temporal_cache::set_timestamp (tree name) m_timestamp[v] = ++m_current_time; } +// Mark a NAME as stale by marking the timestamp as oldest, unless it is +// already "always current". + +inline void +temporal_cache::set_stale (tree name) +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_timestamp.length () || m_timestamp[v] == 0) + return; + m_timestamp[v] = 1; +} + // Set the timestamp to 0, marking it as "always up to date". inline void @@ -1475,6 +1488,15 @@ ranger_cache::update_to_nonnull (basic_block bb, tree name) { r.set_nonzero (type); m_on_entry.set_bb_range (name, bb, r); + // Mark consumers of name stale so they can be recomputed. + if (m_gori.is_import_p (name, bb) || m_gori.is_export_p (name, bb)) + { + tree x; + FOR_EACH_GORI_EXPORT_NAME (m_gori, bb, x) + if (m_gori.in_chain_p (name, x) + && gimple_bb (SSA_NAME_DEF_STMT (x)) == bb) + m_temporal->set_stale (x); + } } } } diff --git a/gcc/testsuite/gcc.dg/pr104530.c b/gcc/testsuite/gcc.dg/pr104530.c new file mode 100644 index 00000000000..9adedc5e5f9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr104530.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +void foo(void); + +static int a, *b = &a, c, d = 1; + +int main() { + c = 0 == b; + a = *b; + if (c % d) + for (; d; --d) + foo(); + b = 0; +} + +/* { dg-final { scan-tree-dump-not "foo" "evrp" } } */ -- 2.17.2