From patchwork Fri Oct 29 14:44:06 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1548062 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=TqsEjZlb; dkim-atps=neutral Authentication-Results: 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=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (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 4HglZV3zspz9sRK for ; Sat, 30 Oct 2021 01:44:49 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4B47D3857C7C for ; Fri, 29 Oct 2021 14:44:47 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4B47D3857C7C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1635518687; bh=/hfIfBPL8rLByOZk2ugH9W+3/qapu/kc1M4eCotjKjg=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=TqsEjZlb+SpGAXFFVYiRfGv6s5OYMTg14C0unKVEjKwNhFEDtLOLWhU3x3om1ysCt o5ljQ2+G+9NwL5mOtqzui3Y2ZPYGb4cTjmP8cyzk4ujLg4GqrOCRNssdPiA6p5FWsQ EYKQMqoXeqiWKh2g9SBuECRcIBNrcoU41be2J0Jc= 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 A0C333857819 for ; Fri, 29 Oct 2021 14:44:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A0C333857819 Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-554-NAniupGfOgSXWIGmtoz2dw-1; Fri, 29 Oct 2021 10:44:09 -0400 X-MC-Unique: NAniupGfOgSXWIGmtoz2dw-1 Received: by mail-qt1-f199.google.com with SMTP id q2-20020a05622a030200b002a7adb98bbfso7003856qtw.14 for ; Fri, 29 Oct 2021 07:44:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:to:from:subject:cc:message-id:date:user-agent :mime-version:content-language; bh=/hfIfBPL8rLByOZk2ugH9W+3/qapu/kc1M4eCotjKjg=; b=yB5hDTzBL93M0kvXs9M+Y8C/wwCEJnP3Ro5PNh2tMeOJS+hOr43ILiX9/OO5BAzi+X RUf5JLk6UKjXyq1Jx9gY7c/AUxox/0GohXN2w+aBn93d7DFOyy7G+f2au6Essf7zfiQW cKUTjhFURymoqvrBnBnMsiOfQG+/OUA5DjQhf4KaM9E45qlZ89s+VZOZNbd0CZEi4oHR cneuAvGKSuG4FsVPwOp4W+QXpi1JoCXw0PDVTgvnFoYwNG7eXLBiHPMyxtWAdTo5WcUf Kfi5cMd+rU7tX5haYwGErlVemvMeuenhli0eGd1LjI89wkW5umjNqsySOxmZVDZqIhmc YqDA== X-Gm-Message-State: AOAM531WW0tmri+4h3SDZB960lxn4377ue+wcybZeIQ3EqAdOM9DetFe KICg+NylPBRKm1FF2Zpsq0JBADoj2glcLfF0esWsHSQhAYvU3AeGRUVeXWxT0w7CnLkm/+RETXt KrLG1I7HKeyo51kvK9w== X-Received: by 2002:a37:b242:: with SMTP id b63mr8919954qkf.346.1635518648671; Fri, 29 Oct 2021 07:44:08 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzC05NgzDkXLPtA1RKOx9A9cgtpr9x8l/ydoOZDOHbTBuelaYobbjPxW9TFg3mVJSJ8nJ8boQ== X-Received: by 2002:a37:b242:: with SMTP id b63mr8919937qkf.346.1635518648470; Fri, 29 Oct 2021 07:44:08 -0700 (PDT) Received: from [192.168.0.102] ([192.24.49.122]) by smtp.gmail.com with ESMTPSA id s7sm2981006qta.3.2021.10.29.07.44.07 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 29 Oct 2021 07:44:07 -0700 (PDT) To: gcc-patches Subject: [COMMITTED] PR tree-optimization/102983 - Perform on-entry propagation after range_of_stmt on a gcond. Message-ID: Date: Fri, 29 Oct 2021 10:44:06 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA 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, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP 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 Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" When range-of_stmt is invoked on a statement, out-of-date updating is keyed off the timestamp on the definition. When the def is calculated, and its global value stored, a timestamp is created for the cache.  if range_of_stmt is invoked again, the timestamp of the uses are compared to the definitions, and if they are older, we simply use the cache value. If one of the uses is newer than the definition, that means an input may have changed, and we will recalculate the definition. If this new value is different, we propagate this new value to any subsequent cache entries In the case of a gcond, there is no LHS, so we ahev no way to determine if anything might be out of date or need updating. Until now, we just did nothing except calculate the branch... any cache entires in the following blocks were never updated.  In this PR, we later determines the b_4 has a value of 0 instead of [0,1] , which would then change the value of c in subsequent blocks. This patch triggers a re-evaluation of all exports from a block when range_of_stmt is invoked on a gcond.  This isnt quite as bad as it seems because:   a) range_of_stmt on a stmt without a LHS  is never invoked from within the internal API, so its only a client like VRP which can make this call   b) The cache propagator is already smart enough to only propagate a value to the following blocks if       1 - there is already an on-entry cache value, otherwise its skipped       2 - the value actually changed. The net result is that this change has very minimal impact on the compile time performance of the ranger VRP pass.. In the order of 0.5%.  It also now catches a few things we use to miss. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From cb596fd43667f92c4cb037a4ee8b2061c393ba60 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 28 Oct 2021 13:31:17 -0400 Subject: [PATCH] Perform on-entry propagation after range_of_stmt on a gcond. Propagation is automatically done by the temporal cache when defs are out of date from the names on the RHS, but a gcond has no LHS, and any updates on the RHS are never propagated. Always propagate them. gcc/ PR tree-optimization/102983 * gimple-range-cache.h (propagate_updated_value): Make public. * gimple-range.cc (gimple_ranger::range_of_stmt): Propagate exports when processing gcond stmts. gcc/testsuite/ * gcc.dg/pr102983.c: New. --- gcc/gimple-range-cache.h | 4 ++-- gcc/gimple-range.cc | 12 +++++++++++- gcc/testsuite/gcc.dg/pr102983.c | 21 +++++++++++++++++++++ 3 files changed, 34 insertions(+), 3 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr102983.c diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 4937a0b305a..75105008338 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -103,6 +103,8 @@ public: bool get_non_stale_global_range (irange &r, tree name); void set_global_range (tree name, const irange &r); + void propagate_updated_value (tree name, basic_block bb); + non_null_ref m_non_null; gori_compute m_gori; @@ -120,8 +122,6 @@ private: void entry_range (irange &r, tree expr, basic_block bb); void exit_range (irange &r, tree expr, basic_block bb); - void propagate_updated_value (tree name, basic_block bb); - bitmap m_propfail; vec m_workback; vec m_update_list; diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 91bacda6dd0..2c9715a6f2c 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -256,7 +256,17 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) // If no name, simply call the base routine. if (!name) - res = fold_range_internal (r, s, NULL_TREE); + { + res = fold_range_internal (r, s, NULL_TREE); + if (res && is_a (s)) + { + // Update any exports in the cache if this is a gimple cond statement. + tree exp; + basic_block bb = gimple_bb (s); + FOR_EACH_GORI_EXPORT_NAME (m_cache.m_gori, bb, exp) + m_cache.propagate_updated_value (exp, bb); + } + } else if (!gimple_range_ssa_p (name)) res = get_tree_range (r, name, NULL); // Check if the stmt has already been processed, and is not stale. diff --git a/gcc/testsuite/gcc.dg/pr102983.c b/gcc/testsuite/gcc.dg/pr102983.c new file mode 100644 index 00000000000..ef58af6def0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr102983.c @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ +void foo(void); + +static int a = 1; + +int main() { + int c = 0; + for (int b = 0; b <= 0; b++) { + if (!a) + foo(); + if (b > c){ + if (c) + continue; + a = 0; + } + c = 1; + } +} + +/* { dg-final { scan-tree-dump-times "Folding predicate c_.* to 1" 1 "evrp" } } */ -- 2.17.2