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: 98470 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp2817297vqo; Wed, 24 May 2023 05:43:38 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5NEVjJajMoZEP95GnW2SSj4aQ8EwsxJceYYVlcToybnF7Nb+enQz+02RicvTachwVdt/eV X-Received: by 2002:a17:907:9449:b0:969:cbf4:98fa with SMTP id dl9-20020a170907944900b00969cbf498famr16257922ejc.65.1684932218601; Wed, 24 May 2023 05:43:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684932218; cv=none; d=google.com; s=arc-20160816; b=CnXnHnsjIGGBPbM618MidKWcNDzUSQss8cMERO0X/D9rUqnAAoHc5ypWm+eDQbDdSP wU+/jgGuHClwMF4mn5DP+Vp3CdFD0oZTHyHespw/Sdcn2G8Ek0iMAoS5yAxBIa2RA3ZW OIh8u9ALcYayYcmRFhQD3Aq9rhWjO7WOpQ9l7WtTbYk7Yv4aBQ3V14WDt2yWQLVPAN8U SPBlthcXN0EPltqbujFbxSBKOwCWgJdyzysL4Bzww3B+ur4OtXVkYl5VuUIYuFcyCkcf QZqhHJhatS0H96/00WyGjE0Y82hKJAfcekuEnmbk+cO5Rq95zkGCnN6e6s5eYY36qFjk kjXw== 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=EGwPH5mhTVEVuIzrzdqIOvS+XsGfV9clRz43Z80MRqc=; b=ZNSnw7xBuUKkk1j5fSzWV30e4RLnopuouHuYJ2/PW/+CNnxaw6Ywh1ug2Hc0AIMnR3 k+khSj2gHbAxzzoUPP3m9R9gK0g6ABz9VOHfzoBjGEX8Qmvwgx87kAjRYe8c9eRnE6QY rdNCj/Qw4Qyg/3ycKIsBTj9BR1XHTvpuRuXjI72WLe7ey4tg874R9XFFevJnpOgaO2fb BnLL9JqDgmBUxpDGvv3qs2aNfaDUPaF7FCJpx0XeHRCBBXchk/iRPyWNaBTzfSobtdRA MhmV1DkW6Z9tJfzjZ3LwWzrA6YF8OUzLxHw6Cy9Y6t3mVaWWlqnnbqSby1L8dg+08Suh kV5w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=n7obAXF6; 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 w20-20020a056402129400b004fbbd7bee7csi6418802edv.58.2023.05.24.05.43.38 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 24 May 2023 05:43:38 -0700 (PDT) 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=n7obAXF6; 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 60A7D383906F for ; Wed, 24 May 2023 12:42:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 60A7D383906F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684932178; 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=n7obAXF65hnxEPma4pvY6Jdjdb8oYbKvnnEj7iw/kuYrdXnDuCtRxEBRBOc3XbybD JT0jkbMUxrrMecq44PGfX6kr0zttQP/K3xCOb38/LMDmOkp7uy0ysaLvck9/ID1soF S+TDFZy6JBZXpnKk2P5FEFJTfWg9prKNefhGiO1I= 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-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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1766779485969463790?= X-GMAIL-MSGID: =?utf-8?q?1766779485969463790?= 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: 98473 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp2817930vqo; Wed, 24 May 2023 05:44:50 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5ZJUFjUBA8bsCUUPKCt9ouWm/g6BOUrTXiRNcp1CPbFb33qQX3hvwH9zNSOYCwAXkSlQGa X-Received: by 2002:aa7:c646:0:b0:50d:9de4:5664 with SMTP id z6-20020aa7c646000000b0050d9de45664mr1638785edr.40.1684932290156; Wed, 24 May 2023 05:44:50 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684932290; cv=none; d=google.com; s=arc-20160816; b=yuoay5ALQ/PiTKzc0XKIHxGQJlk4tBWC6mnK0QiZad0X+JtY6TUXChg7yfANk8zaBV HXcpuUj1g0sH2O1lh2g9ZZXmhNuhqbASYtSBsHbxRKqn+QK1s7U11f7Ibm1M+M1+e034 AcNAk6kDvDI1yf+R3KH7pAeTL6PxvtgPishq1U6Wdw8m/GvhoLhm650+p4xIBKpY+Y2r UR2YnseaTpLwwQRC/APYWeesKRoxt1z9fzeYJpVz8AwNUMZ7a2ZyGkF9mMA6RqXzAXc7 mn6DYY/3MvzJaGoMhFrm7Syf/wLoD2hsVeSxVHcVEsakDu4SOWjZDeqmdHFO55hEDVWC kvnw== 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=SB6aJ9+TpVuZ72vuAaQ9b5EW/ZwbM0kRma/a5rJQ4to=; b=udyoNjp3hQqeNZ5N0PFSf0yLfdg2E+/9g58rauDYrPuKDkXpZ7ktKbaxT8xAjVojgo dgCnvaF5jTuB3NrMQoyPE/ns+tZy3Nb0UClhqfVtcg8Rzn02ZU9TBtnj+jUi9ocEBXWN zxFVl9XyqKJdb3aR67Z8wi4LHAkuPpSAnJ+GV0dn/U8Yn2Ue8seLzBm9v/HHS1PPsVam MeaMI6E7/dKjAeJjHCJpu/2Wv8Not3k1HaHPI2EBNuhUqzDjqnDpHrUOrpNqJ7mw4gjU Nb2pvZpn7/LTKssR+DmV/QXev5jJnNUK8w9T0ERshrLgPsSyDeNRZMzdEPy0WAlpdzJx 2IUg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=YZ+kp0eQ; 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 (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id n8-20020aa7c448000000b00506bd4fba2asi1295291edr.319.2023.05.24.05.44.49 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 24 May 2023 05:44:50 -0700 (PDT) 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=YZ+kp0eQ; 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 1908238768BB for ; Wed, 24 May 2023 12:43:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1908238768BB DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684932221; 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=YZ+kp0eQ8oGea7oP/N0OHl6RY9RvU4ggrclBm1Ie+cRWSn5qrUoTZzqlRxX64ef9Z kQ5TKz7ikX4jqQsLU3zgv1ApPF43wouUfLMzrQF4RfOMytNCiJZEZQP6DLgDcGY2nU XbxLA4Ci8YxqJa2cEFhvh7iSbMznI3jB9Od2pmCE= 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-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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1766779561188141000?= X-GMAIL-MSGID: =?utf-8?q?1766779561188141000?= 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: 98472 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp2817763vqo; Wed, 24 May 2023 05:44:31 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6MY+m1FKriInRQSGLbtkvgGzVTsE4eIF9HeIjkyzISapDxHs14dDrzsNYOEKo6nS3xIhOg X-Received: by 2002:a17:907:6da9:b0:96f:bab6:4db5 with SMTP id sb41-20020a1709076da900b0096fbab64db5mr14150871ejc.28.1684932271327; Wed, 24 May 2023 05:44:31 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1684932271; cv=none; d=google.com; s=arc-20160816; b=DIjxyJHOtV5heIUybS5k7VPuaFaKDFQm5UUKTgidiycEmRKJZu0pJ8gq52iB32ZiFY 4yu7hgWPW63h8C2jEZtGHbwnor1jSdTs2cR9KShaHbO3p35EkjTQ1Jowo9f/bM5z5uYR IQsVW1daeWY4Ng6o86uO+5Y+xvhjIvPrln1ahSsU1TT4XGQu+K92l0jc6E2v7MopoWrd LNQ3T/d5+s47VFFiEECe9IWjj9mNlgbEtVTB/ogspubm16I0GDtHjJkFjWqXzX4/TFKz AYu9SggSw1DY6nUTgN/cLaC6KHlNxMC0GjP5UQ2ux9u5X+couaYvNnqglG6YWNE7qAyw RHMA== 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=gVf7tqErHsBZHxmzEEKk6pGABNqwmCuYDt34riCixzE=; b=bGx2sDGn9SBTo60D8T0tV2okTmRiFO8ZuNkp2i01DFdS9D2Ng92+EZ1mAa+XHgmhOF 6CPzPU6MtnOF4ytP5PrkEewjp0KRMPkdEXApH0cC7MCMG7O4o/nWwvNzAcbtKUKkuczY BYllZ4n0qXHpfUE7qRaXk40BNNRXCjwQM3qlL4uMbrGtwhaKZDKfZ1/sT693lgqzKDUo s7idI+zEu0JzxZZOegyD0cTwsFH9fpqm/2YCOg6VQZWyEQLcyru1lySNZlFZy5+jDImK +ulJ4zgd+cCHxtPzP4DCgF6AWy4+CzfizkZvOm/3WFbV/pWUNX+zOq7gMMp6umbwl87D 8IKg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=vMdwsf0F; 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 (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id sb27-20020a1709076d9b00b0097381ff4686si1390497ejc.643.2023.05.24.05.44.31 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 24 May 2023 05:44:31 -0700 (PDT) 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=vMdwsf0F; 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 95549385842D for ; Wed, 24 May 2023 12:43:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 95549385842D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684932205; bh=gVf7tqErHsBZHxmzEEKk6pGABNqwmCuYDt34riCixzE=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=vMdwsf0FK2EKIJ5dTuTdql3jVfCXDpF/NF9T1p/nRk/+I2iq89Hq5u0SlixOuvvwf lMTojtGvB+w6rblUyHl2fp5QO3L9u3bKHpjvt9Ag2qCB/1eSWPMVifMFlwjNRff1Z2 S0hezcwuvSxuMgE/bSRbqVyCnYoc7qcK7hpyBkzA= 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-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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1766779541265805476?= X-GMAIL-MSGID: =?utf-8?q?1766779541265805476?= 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