From patchwork Wed May 24 12:42:07 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1785720 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org 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=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) 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=VCFgxIwK; dkim-atps=neutral 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 ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QR9nR3k6kz20Q6 for ; Wed, 24 May 2023 22:42:35 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 898B33858004 for ; Wed, 24 May 2023 12:42:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 898B33858004 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684932153; bh=EGwPH5mhTVEVuIzrzdqIOvS+XsGfV9clRz43Z80MRqc=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=VCFgxIwKFEXpngaiPdIO2Lmj+2rJHjl0mxVg1dlPUdKnAjeNeQ7nF+WCNAe/mezv6 /G7nH8QQgMeflyp33yK3AarXykohzcHvfoSwvnYQ6bFvNtLUKEI5ZPTNj+A5oQhuyi oiNnAlhwx7ZCt2J6EZHoYVXIK7CrGpzGRwVoR6J4= 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 2DF44385700C for ; Wed, 24 May 2023 12:42:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2DF44385700C Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-266-Pd-_rXrXMd-tTlNLHiekrw-1; Wed, 24 May 2023 08:42:10 -0400 X-MC-Unique: Pd-_rXrXMd-tTlNLHiekrw-1 Received: by mail-qv1-f69.google.com with SMTP id 6a1803df08f44-621257e86daso12524576d6.1 for ; Wed, 24 May 2023 05:42:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684932129; x=1687524129; 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=KxIwf/DD6d2C8iJHuUPOlF06DU+m7d+4zc2rTKf2qcg=; b=lUVIaRCIKeDfthlvR2orLhvZphJibAaAC2SgubuGz5byQzRXnt0b77KaZh8IsBQ/zs 8Iw/Pw7myPQTh1+RqbMYS14mXM5qTO+APQ0DhKqz2sTsys1TDaKORZ7FapDBywXmxCis b32twFq+WgLVYWXl8Pt9i1z8grMOD0GqQkZrcQ2KUW0dOKsRgjGjOzV/0q9ZqRRYW4st NUwv8gzhGY4jJ4Akb2Wigp8a0gCUL719tqYtleszqJTB+ZjoxA/ZfauApCjJDrVgZHyr CgzQ9coixtAUrCc76Jv/+fePTPtzP3hKmm/0pwA+mLerop+r4IQG+xMsGisU9kWrNCxT A+Bg== X-Gm-Message-State: AC+VfDwEYu6xHdHZw2+ikrnVyUP4191QeDXHmblO3a5BHQApEaeKoL6Y IVnR7jDneTsBb+VNJnbu8DswExaXpnEEGTb7VzMI23wBOZjBWuOjtj8ijZskfHfF6fZpO/seLrP LqpbEPcophOMWB1x+K/LkjAz/C2Huh7CYzQieQuF9sfxge6gqeLAisgdZI9mcCTeEb5UVMzrsnR fsTQ== X-Received: by 2002:ad4:5d4e:0:b0:623:690c:3ce6 with SMTP id jk14-20020ad45d4e000000b00623690c3ce6mr29737228qvb.32.1684932129072; Wed, 24 May 2023 05:42:09 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ64mskIFeuK7BND24l6NmpRYYLyk0LxuWIRaTjbJ0pPMhgihIDrShKkWI3rnF7bCfiNJ+52LQ== X-Received: by 2002:ad4:5d4e:0:b0:623:690c:3ce6 with SMTP id jk14-20020ad45d4e000000b00623690c3ce6mr29737209qvb.32.1684932128708; Wed, 24 May 2023 05:42:08 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id et4-20020a056214176400b005fdbcab3065sm3537243qvb.72.2023.05.24.05.42.07 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 May 2023 05:42:08 -0700 (PDT) Message-ID: Date: Wed, 24 May 2023 08:42:07 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 1/3] PR tree-optimization/109695 - Choose better initial values for ranger. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, 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-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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Instead of defaulting to an initial value of VARYING before resolving cycles, try folding the statement using available global values instead.  THis can give us a much better initial approximation, especially in cases where there are no dependencies, ie    f_45 = 77 This implements suggestion 2) in comment 22 of the PR: 2) The initial value we choose is simply VARYING. This is why 1) alone won't solve this problem.  when we push _1947 on the stack, we set it to VARYING..  then proceed down along chain of other dependencies Driven by _1011 which are resolved first. When we get back to _1947 finally, we see:   _1947 = 77; which evaluated to [77, 77], and is this different than VARYING, and thus would cause a new timestamp to be created even if (1) were implemented. TODO: When setting the initial value in the cache, rather than being lazy and using varying, we should invoke fold_stmt using get_global_range_query ().   This will fold the stmt and produce a result which resolved any ssa-names just using known global values. THis should not be expensive, and gives us a reasonable first approximation.  And for cases like _1947, the final result as well. I stop doing this after inlining because there are some statements which change their evaluation (ie, BUILTIN_IN_CONSTANT)  which causes headaches... and then we  just default to VARYING again or anything which doesn't have a  global SSA range set.. There is a 2.7% hit to VRP to evaluate each statement this additional time, but only 0.09% to overall compile time. Besides, we get it back later in the patch set.. :-) Bootstraps on x86_64-pc-linux-gnu with no regressions.   Pushed. Andrew From 3a20e1a33277bcb16d681b4f3633fcf8cce5a852 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 23 May 2023 15:11:44 -0400 Subject: [PATCH 1/3] Choose better initial values for ranger. Instead of defaulting to VARYING, fold the stmt using just global ranges. PR tree-optimization/109695 * gimple-range-cache.cc (ranger_cache::get_global_range): Call fold_range with global query to choose an initial value. --- gcc/gimple-range-cache.cc | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 07c69ef858a..8ddfd9426c0 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -951,7 +951,22 @@ ranger_cache::get_global_range (vrange &r, tree name, bool ¤t_p) || m_temporal->current_p (name, m_gori.depend1 (name), m_gori.depend2 (name)); else - m_globals.set_range (name, r); + { + // If no global value has been set and value is VARYING, fold the stmt + // using just global ranges to get a better initial value. + // After inlining we tend to decide some things are constant, so + // so not do this evaluation after inlining. + if (r.varying_p () && !cfun->after_inlining) + { + gimple *s = SSA_NAME_DEF_STMT (name); + if (gimple_get_lhs (s) == name) + { + if (!fold_range (r, s, get_global_range_query ())) + gimple_range_global (r, name); + } + } + m_globals.set_range (name, r); + } // If the existing value was not current, mark it as always current. if (!current_p) -- 2.40.1 From patchwork Wed May 24 12:42:21 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1785722 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) 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=RahJ7RTr; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QR9pD69lRz20Q6 for ; Wed, 24 May 2023 22:43:16 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C947238323E8 for ; Wed, 24 May 2023 12:43:14 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C947238323E8 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684932194; bh=SB6aJ9+TpVuZ72vuAaQ9b5EW/ZwbM0kRma/a5rJQ4to=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=RahJ7RTrKG8EPnJoumOLrOnK0aKCURAoB3+t58PPIywLLcA3cGou7UumMyIIgjAS5 qO1I+yxDVLsFHXWj4HI8r03p9EGmwRrJ3CD5i6zbxSjaEe4kgyNT3fO6GWnW83o5uz Cz0n3dOPqKHgvBgHGxdEOMnq85mq5fQl8d0147O0= 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 A91FD385770B for ; Wed, 24 May 2023 12:42:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A91FD385770B Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-267-EaFm-y-_O82BKFoyIIzRiQ-1; Wed, 24 May 2023 08:42:24 -0400 X-MC-Unique: EaFm-y-_O82BKFoyIIzRiQ-1 Received: by mail-qt1-f197.google.com with SMTP id d75a77b69052e-3f6afd58c32so5941991cf.3 for ; Wed, 24 May 2023 05:42:24 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684932143; x=1687524143; 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=82uwTGn6LION0y0K0UhqBP+mObU6kRmu2onRvFS+xho=; b=mHA5fwn2QZedTu13GHzbqptGuZWR99Zn7eFF1ymBLm1wl7JrJFIVkcWAnHwHMjIblR GTxdjzsKGwt9FA20xrr7PHwWERvXIYsL+Dcj6adRnpb7vNywKMqHKOZ7w7X/gpDETyJV IF8jhWpj0duZeiuZjrWfIOqCouAKU/2PBjDBuha9eVQvEjoQ2TnuGEkcCa67GtShrleC 94uZbLHuuP/mp0SvdHQwWYaLzVNRZ7E9s0U/YMU1JpbVPGIntAelB+rYRO8ev/mKQpLf qq6vIvDjQyMdAwnHzwq8dq5wZ3+icXMyfZc6+80wQvGmIV/jIIZg8OAciy0WaTASc70y mVxw== X-Gm-Message-State: AC+VfDwXW3plB5Z/3ysLLIpm9XQPHnTpUeqBy1jGJClOTL0IKQKL/O+h GHlOtttZVN70yCgdHqKSxNqVFbH9gQS/uIHjE+3u65ztVqVT5rSi4ROI7Eht7GyWgp45cS+Xy/d cVg9GgwemwDxWE5EH0U7RZeSvEAbACdQWJXVNhUdNHMQiQYFXYhlSP30gygMep3GsFjicjEAE/W rYHg== X-Received: by 2002:ac8:7f48:0:b0:3f6:c609:e9da with SMTP id g8-20020ac87f48000000b003f6c609e9damr1507174qtk.44.1684932143653; Wed, 24 May 2023 05:42:23 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6kyPC6oogRnY3M4hjglLQraQGt6Fxr66Z+6IETPwOeVdVc8zOYg+4Wm3TrQLC7cXszxKzjCQ== X-Received: by 2002:ac8:7f48:0:b0:3f6:c609:e9da with SMTP id g8-20020ac87f48000000b003f6c609e9damr1507126qtk.44.1684932143091; Wed, 24 May 2023 05:42:23 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id mx15-20020a0562142e0f00b0061fb6cc2051sm3538968qvb.15.2023.05.24.05.42.22 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 May 2023 05:42:22 -0700 (PDT) Message-ID: <74f5eb7b-fd29-640c-9704-4756d36e207a@redhat.com> Date: Wed, 24 May 2023 08:42:21 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 2/3] PR tree-optimization/109695 - Use negative values to reflect always_current in the, temporal cache. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, 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-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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This implements suggestion 3) from the PR: 3) When we first set the intial value for _1947 and give it the ALWAYS_CURRENT timestamp, we lose the context of when the initial value was set.  So even with 1) & 2) implemented, we are *still* need to set a timestamp for it when its finally calculated, even though it is the same as the original.  This will cause any names already evaluated using its range to become stale because we can't leave it as ALWAYS_CURRENT.    (There are other places where we do need to be able to re-evaluate.. there are 2 testsuite failures caused by this if we just leave it as always_current) TODO: Alter the implementation of ALWAYS_CURRENT such that a name is also given a timestamp at the time of setting the initial value.   Then set_global_range() will clear the ALWAYS_CURRENT tag unconditionally, but leave the original timestamp if the value hasn't changed.  This will then provide an accurate timestamp for the initial_value. Instead of using 0, I changed the timestamp from unsigned to an integer, and used a negative value to indicate it is always current.  This has very little performance impact.  Bootstraps on x86_64-pc-linux-gnu with no regressions.   Pushed. Andrew From 5ed159fdda4d898bdda49469073b9202f5a349bf Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 23 May 2023 15:20:56 -0400 Subject: [PATCH 2/3] Use negative values to reflect always_current in the temporal cache. Instead of using 0, use negative timestamps to reflect always_current state. If the value doesn't change, keep the timestamp rather than creating a new one and invalidating any dependencies. PR tree-optimization/109695 * gimple-range-cache.cc (temporal_cache::temporal_value): Return a positive int. (temporal_cache::current_p): Check always_current method. (temporal_cache::set_always_current): Add param and set value appropriately. (temporal_cache::always_current_p): New. (ranger_cache::get_global_range): Adjust. (ranger_cache::set_global_range): set always current first. --- gcc/gimple-range-cache.cc | 43 +++++++++++++++++++++++++++------------ 1 file changed, 30 insertions(+), 13 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 8ddfd9426c0..db7ee8eab4e 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -701,12 +701,12 @@ public: ~temporal_cache (); bool current_p (tree name, tree dep1, tree dep2) const; void set_timestamp (tree name); - void set_always_current (tree name); + void set_always_current (tree name, bool value); + bool always_current_p (tree name) const; private: - unsigned temporal_value (unsigned ssa) const; - - unsigned m_current_time; - vec m_timestamp; + int temporal_value (unsigned ssa) const; + int m_current_time; + vec m_timestamp; }; inline @@ -725,12 +725,12 @@ temporal_cache::~temporal_cache () // Return the timestamp value for SSA, or 0 if there isn't one. -inline unsigned +inline int temporal_cache::temporal_value (unsigned ssa) const { if (ssa >= m_timestamp.length ()) return 0; - return m_timestamp[ssa]; + return abs (m_timestamp[ssa]); } // Return TRUE if the timestamp for NAME is newer than any of its dependents. @@ -739,13 +739,12 @@ temporal_cache::temporal_value (unsigned ssa) const bool temporal_cache::current_p (tree name, tree dep1, tree dep2) const { - unsigned ts = temporal_value (SSA_NAME_VERSION (name)); - if (ts == 0) + if (always_current_p (name)) return true; // Any non-registered dependencies will have a value of 0 and thus be older. // Return true if time is newer than either dependent. - + int ts = temporal_value (SSA_NAME_VERSION (name)); if (dep1 && ts < temporal_value (SSA_NAME_VERSION (dep1))) return false; if (dep2 && ts < temporal_value (SSA_NAME_VERSION (dep2))) @@ -768,12 +767,28 @@ temporal_cache::set_timestamp (tree name) // Set the timestamp to 0, marking it as "always up to date". inline void -temporal_cache::set_always_current (tree name) +temporal_cache::set_always_current (tree name, bool value) { unsigned v = SSA_NAME_VERSION (name); if (v >= m_timestamp.length ()) m_timestamp.safe_grow_cleared (num_ssa_names + 20); - m_timestamp[v] = 0; + + int ts = abs (m_timestamp[v]); + // If this does not have a timestamp, create one. + if (ts == 0) + ts = ++m_current_time; + m_timestamp[v] = value ? -ts : ts; +} + +// Return true if NAME is always current. + +inline bool +temporal_cache::always_current_p (tree name) const +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_timestamp.length ()) + return false; + return m_timestamp[v] <= 0; } // -------------------------------------------------------------------------- @@ -970,7 +985,7 @@ ranger_cache::get_global_range (vrange &r, tree name, bool ¤t_p) // If the existing value was not current, mark it as always current. if (!current_p) - m_temporal->set_always_current (name); + m_temporal->set_always_current (name, true); return had_global; } @@ -979,6 +994,8 @@ ranger_cache::get_global_range (vrange &r, tree name, bool ¤t_p) void ranger_cache::set_global_range (tree name, const vrange &r) { + // Setting a range always clears the always_current flag. + m_temporal->set_always_current (name, false); if (m_globals.set_range (name, r)) { // If there was already a range set, propagate the new value. -- 2.40.1 From patchwork Wed May 24 12:42:27 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1785721 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) 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=IYislzKs; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QR9ny52S1z20Q6 for ; Wed, 24 May 2023 22:43:02 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 93A383836E80 for ; Wed, 24 May 2023 12:43:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 93A383836E80 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684932180; bh=gVf7tqErHsBZHxmzEEKk6pGABNqwmCuYDt34riCixzE=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=IYislzKsVtLWo/9pqQEJFIsuu8VlE3a+X9S8idP++HGbyJ44vuyPNn5O050TTMG8E gb7lRscD2gCbOK9ubfaMj/GD4czXhhEZxN2av8Z0AyUaaG2JVV3/LcBE+ztkpWMlQJ N9dVMOeefF0qinFVoxZ/ctOJ3ftefvsdloz9+Dmw= 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 C63A83856DC7 for ; Wed, 24 May 2023 12:42:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C63A83856DC7 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_256_GCM_SHA384) id us-mta-195-oI-Ps45tN2Oig3TI-oWGTw-1; Wed, 24 May 2023 08:42:30 -0400 X-MC-Unique: oI-Ps45tN2Oig3TI-oWGTw-1 Received: by mail-qv1-f72.google.com with SMTP id 6a1803df08f44-623998c0d33so7244546d6.0 for ; Wed, 24 May 2023 05:42:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684932149; x=1687524149; 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=vIvi355OMzO2Ail3uJWMGHtsoGkczA4zlYlopkq3RCY=; b=Vu1wJ98c0uZ/128z4ejcY8h2t1tNUDoLLo1MFGMiZ54gtUOiMEYg19Bgn5cLBbfeXw gaLWIl5JKMS+vH3JcfCbeNgQcL5gTLRP1Jv5P8Co95ZjJ8EHkq5axpOctyi3ieCc4EhW diD6sXiYdg+H22X62sCmpx1glwt9hF+XfVsoCYRD/aXPlBtqAhGBXNoac9w7fhygaU/H IyqZS3b4WbrcRaIFdbBc+PYmV8XSymm/sI1aVCjUjBn+aESWz7cXW6koaTTL3f8vv5ch HNZD71nVIWaoYE0VQ+Sdn7yv4ckcjbPc8E6JWqCrmtpNL1wvhXXQ0fEr66O0AIbNqPG+ DENw== X-Gm-Message-State: AC+VfDxQQc48YCb3Bc3+ygzJBUTT/TbiF0Jnq0DSMJhe96sCcnn2odHS i7nk+imo8KyJpxYnqVRsTJnXmB8dckO2QP2zCbf8beI99TPodj18aZoVgF4kuAVDaReH9jM2T4d sLEQX9VLBw1OzbakqU0g5iPZVqMqyk8v+LW/CRTqDVrAT86DzClUS6XkAsSAAo2HGCz4uGrZDMp KZlw== X-Received: by 2002:a05:6214:410d:b0:625:9578:990e with SMTP id kc13-20020a056214410d00b006259578990emr5294091qvb.23.1684932149661; Wed, 24 May 2023 05:42:29 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7hjIEpwROBOaDNZPkwHRmcexKU9kTWRkn7Q5E4UMrK9DXOqTQW1jXGY2v8D6Yf3rgwKvhDKA== X-Received: by 2002:a05:6214:410d:b0:625:9578:990e with SMTP id kc13-20020a056214410d00b006259578990emr5294071qvb.23.1684932149275; Wed, 24 May 2023 05:42:29 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::933? ([2607:fea8:51df:4200::933]) by smtp.gmail.com with ESMTPSA id mm19-20020a0562145e9300b00623927281c2sm3536239qvb.40.2023.05.24.05.42.28 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 24 May 2023 05:42:28 -0700 (PDT) Message-ID: <419533f4-b632-ad55-f225-8f8dd6fd709b@redhat.com> Date: Wed, 24 May 2023 08:42:27 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 3/3] PR tree-optimization/109695 - Only update global value if it changes. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, 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-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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch implements suggestion 1) from the PR: 1) We unconditionally write the new value calculated to the global cache once the dependencies are resolved.  This gives it a new timestamp, and thus makes any other values which used it out of date when they really aren't.   This causes a lot of extra churn. TODO: This should be changed to only update it when it actually changes.  Client code shouldn't have to do this, it should be handled right int the cache's set_global_value (). It turns out it is about a 3% compilation speed hit to compare the ranges every time we set them, which loses any gains we see. As such, I changed it so that set_global_range takes an extra parameter which indicates whether the value has changed or not. In all cases, we have the result of intersection which gives us the information for free, so we might as well take advantage of it.  instead we get about a 2.7% improvement in speed in VRP and another 0.7% in threading. set_global_range now checks the changed flag, and if it hasnt changed, checks to see if the value is current or not, and only gives the result a new timestamp if its out of date.  I found many cases where we   1) initally calculate the result, give it a timestamp,   2) then evaluate the dependencies.. which get fresher timestamps than the result   3) the initial result turns out to still be right, so we dont have to propagate the value or change it. However, if we do not give it a fresh time stamp in this case, it wil be out of date if we ever check is sine the dependencies are fresher.   So in this case, we give it a new timestamp so we wont re-evaluate it. The 3 patches together result in VRP being just 0.15% slower, threading being 0.6% faster, and overall compilation improves by 0.05% It will also compile the testcase from the PR with issues after reverting Aldy's memory work and using int_range_max as int_range<255> again.. so that is also an indication the results are worthwhile. At this point, I don't think its worth pursuing suggestion 4 from the PR.. it is wrought with dependency issues that I don't think we need to deal with at this moment.  When I have more time I will give it more consideration. Bootstraps on x86_64-pc-linux-gnu with no regressions.   Pushed. Andrew From c3c1499498ff8f465ec7eacce6681c5c2da03a92 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 23 May 2023 15:41:03 -0400 Subject: [PATCH 3/3] Only update global value if it changes. Do not update and propagate a global value if it hasn't changed. PR tree-optimization/109695 * gimple-range-cache.cc (ranger_cache::get_global_range): Add changed param. * gimple-range-cache.h (ranger_cache::get_global_range): Ditto. * gimple-range.cc (gimple_ranger::range_of_stmt): Pass changed flag to set_global_range. (gimple_ranger::prefill_stmt_dependencies): Ditto. --- gcc/gimple-range-cache.cc | 10 +++++++++- gcc/gimple-range-cache.h | 2 +- gcc/gimple-range.cc | 8 ++++---- 3 files changed, 14 insertions(+), 6 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index db7ee8eab4e..e069241bc9d 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -992,10 +992,18 @@ ranger_cache::get_global_range (vrange &r, tree name, bool ¤t_p) // Set the global range of NAME to R and give it a timestamp. void -ranger_cache::set_global_range (tree name, const vrange &r) +ranger_cache::set_global_range (tree name, const vrange &r, bool changed) { // Setting a range always clears the always_current flag. m_temporal->set_always_current (name, false); + if (!changed) + { + // If there are dependencies, make sure this is not out of date. + if (!m_temporal->current_p (name, m_gori.depend1 (name), + m_gori.depend2 (name))) + m_temporal->set_timestamp (name); + return; + } if (m_globals.set_range (name, r)) { // If there was already a range set, propagate the new value. diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 946fbc51465..871255a8116 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -117,7 +117,7 @@ public: bool get_global_range (vrange &r, tree name) const; bool get_global_range (vrange &r, tree name, bool ¤t_p); - void set_global_range (tree name, const vrange &r); + void set_global_range (tree name, const vrange &r, bool changed = true); void propagate_updated_value (tree name, basic_block bb); diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index a275c090e4b..4fae3f95e6a 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -320,8 +320,8 @@ gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name) // Combine the new value with the old value. This is required because // the way value propagation works, when the IL changes on the fly we // can sometimes get different results. See PR 97741. - r.intersect (tmp); - m_cache.set_global_range (name, r); + bool changed = r.intersect (tmp); + m_cache.set_global_range (name, r, changed); res = true; } @@ -393,8 +393,8 @@ gimple_ranger::prefill_stmt_dependencies (tree ssa) // Make sure we don't lose any current global info. Value_Range tmp (TREE_TYPE (name)); m_cache.get_global_range (tmp, name); - r.intersect (tmp); - m_cache.set_global_range (name, r); + bool changed = tmp.intersect (r); + m_cache.set_global_range (name, tmp, changed); } continue; } -- 2.40.1