From patchwork Mon Feb 7 14:29:30 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1589317 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=NbCIIDX2; 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 (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 RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4JspTV1lCwz9s8q for ; Tue, 8 Feb 2022 01:30:37 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5EF22385841C for ; Mon, 7 Feb 2022 14:30:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5EF22385841C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1644244234; bh=/F5E7xOuV/tdOp9IygxYEM0FPRme50msABJzJ4lO3Ds=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=NbCIIDX2cMz8oZeWJPv+I3PX7/bDlNOKZlQJIZ7IXF/wTSoiSs5XI1Ix5xilxPrqX A1Zbz8iZIw0Xhfik2hVISy8Bf2TKL8w9T8R2EgJGdW98sChWYNft4dMXJvv761lJrD EXCQQLEvta7srceRCg2ObfU0ZDP6I8Cq++4mrAbA= 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 8D79A385840C for ; Mon, 7 Feb 2022 14:29:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8D79A385840C 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.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-479-TVk6e4U0OJGyVcRIyUmtqg-1; Mon, 07 Feb 2022 09:29:33 -0500 X-MC-Unique: TVk6e4U0OJGyVcRIyUmtqg-1 Received: by mail-qv1-f69.google.com with SMTP id t3-20020a0562140c6300b00424a0fd3721so8765130qvj.12 for ; Mon, 07 Feb 2022 06:29:33 -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:from:subject:to; bh=k74v9ZbyYuQEcfD/wc3WFQFz+l193vJZh8r/02nFgjU=; b=AUgJNVT/YHnQLmp8CfiKGeKecUGNJcQBALPQfyEuDFQAqH0FW/sFkONrTZXUQvmvgI 5rtN0hGtaXlroEBe1dQyk3tmLzUHMFpibdK/r88sMzRzuUuPC2a/GzRCeHdhtGN3UJbr j3KxI5IxDfe75UIH4GBFnIzYHhcdyK4d9Bn8wVp3uTJDxxj1dppPupxE/WMkp4+aYz7c 5Uy5GaxIMab1qTtqNzuWvYh7zH92laO3agmTy96hiRK+0NLRJsf+gV+zAouASnpkePN1 3prrZBglcGUlRdEOLii9S1zBa3lEsmZa0YHqPbCM7AqlCsiOXu7ZrOg1kM9HtwyQYZUb mQbA== X-Gm-Message-State: AOAM533Igoc1xR7UH58dvnU95xgwxWoRNaHrEXBfslzsFJL3QzVE9vg8 9kt8tNhS0PIrBu4Dwkaqs1zCRX8vhKzM9ENd7GDusxWkjmyI3khITmNUtM1CTCKN+VP/e2wBCNd oLZYGgO+DLPJW1Lr9MZ2BR2tPAB/XD5BKWQzdWZ9/FsZpR7XjPcxDMcEmY793y94njefY2w== X-Received: by 2002:ad4:5bae:: with SMTP id 14mr10315094qvq.43.1644244172942; Mon, 07 Feb 2022 06:29:32 -0800 (PST) X-Google-Smtp-Source: ABdhPJx6Z3j7Sp/LcHQG2XMkme9J5+lNBNLhAhMe65/mtDdzqzspUjiQtcFZ0J4afryYby6MoFjDfA== X-Received: by 2002:ad4:5bae:: with SMTP id 14mr10315074qvq.43.1644244172577; Mon, 07 Feb 2022 06:29:32 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id t1sm5678297qtw.17.2022.02.07.06.29.31 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Feb 2022 06:29:31 -0800 (PST) Message-ID: <9290aef2-9c8a-8037-2e59-2496103a5ddc@redhat.com> Date: Mon, 7 Feb 2022 09:29:30 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.5.1 Subject: [PATCH 1/4] tree-optimization/104288 - Change non-null tracking from one bit to a pair. To: gcc-patches , aldy Hernandez X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-11.8 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, 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 Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch changes the non-null tracking in ranger to use 2 bits in order to distinguish between blocks which contain uses of NAME in:   1) non-null generating statements,  (1 bit)   2) statements which are not non-null generating (the other bit),  THis is the new bit.   3) and the existence of both.  (both bits) It utilizes the aligned_chunk sparse bitmap code to track these states for each name, and has zero impact on functionality otherwise as the nonnull_deref_p routine still keys off a non-null access anywhere in the block.   This ensure we add the new capabilities without affected code generation or anything else. There is a get/set routines, but internally i usually defer directly to the get/set_aligned_chunk routine for efficiency.  The overall impact is under .5% of EVRP/VRP compile time.  Most of the additional time is due to now setting a bit for all uses, even if the non-null property isnt set. Bootstraps with no regressions.  OK for trunk? Andrew From 6cd863984a6bf49dc5d6ff00a510003679842e74 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 2 Feb 2022 14:43:29 -0500 Subject: [PATCH 1/3] Change non-null tracking from one bit to a pair. This patch changes the non-null tracking in ranger to use 2 bits in order to distinguish between blocks which contain uses of NAME in: 1) non-null generating statements, 2) statements which are not non-null, 3) and the existance of both. * gimple-range-cache.cc (non_null_ref::get_bb_state): New. (non_null_ref::set_bb_state): New. (non_null_ref::non_null_deref_p): Use new 2 bit values. (non_null_ref::process_name): Use new 2 bit values. * gimple-range-cache.h (class non_null_ref): New prototypes. --- gcc/gimple-range-cache.cc | 82 ++++++++++++++++++++++++++++----------- gcc/gimple-range-cache.h | 2 + 2 files changed, 62 insertions(+), 22 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 16c881b13e1..52094f0bc6a 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -33,6 +33,13 @@ along with GCC; see the file COPYING3. If not see #define DEBUG_RANGE_CACHE (dump_file \ && (param_ranger_debug & RANGER_DEBUG_CACHE)) +// 2 bits represent whether a non_zero or varying use were seen in a block. + +#define NN_NONE 0 +#define NN_VARYING 1 +#define NN_NON_ZERO 2 +#define NN_BOTH (NN_VARYING | NN_NON_ZERO) + // During contructor, allocate the vector of ssa_names. non_null_ref::non_null_ref () @@ -50,16 +57,26 @@ non_null_ref::~non_null_ref () m_nn.release (); } -// Return true if NAME has a non-null dereference in block bb. If this is the -// first query for NAME, calculate the summary first. -// If SEARCH_DOM is true, the search the dominator tree as well. +// Return the non-null state of NAME in block BB. -bool -non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom) +unsigned long +non_null_ref::get_bb_state (tree name, basic_block bb) { - if (!POINTER_TYPE_P (TREE_TYPE (name))) - return false; + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_nn.length ()) + m_nn.safe_grow_cleared (num_ssa_names + 1); + + if (!m_nn[v]) + process_name (name); + + return bitmap_get_aligned_chunk (m_nn[v], bb->index, 2); +} +// Set the non-null state of NAME in block BB to VAL. + +void +non_null_ref::set_bb_state (tree name, basic_block bb, unsigned long val) +{ unsigned v = SSA_NAME_VERSION (name); if (v >= m_nn.length ()) m_nn.safe_grow_cleared (num_ssa_names + 1); @@ -67,7 +84,22 @@ non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom) if (!m_nn[v]) process_name (name); - if (bitmap_bit_p (m_nn[v], bb->index)) + gcc_checking_assert (val <= NN_BOTH); + bitmap_set_aligned_chunk (m_nn[v], bb->index, 2, val); +} + +// Return true if NAME has a non-null dereference in block bb. If this is the +// first query for NAME, calculate the summary first. +// If SEARCH_DOM is true, the search the dominator tree as well. + +bool +non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom) +{ + unsigned v = SSA_NAME_VERSION (name); + if (!POINTER_TYPE_P (TREE_TYPE (name))) + return false; + + if (get_bb_state (name, bb) >= NN_NON_ZERO) return true; // See if any dominator has set non-zero. @@ -81,7 +113,7 @@ non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom) for ( ; bb && bb != def_dom; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) - if (bitmap_bit_p (m_nn[v], bb->index)) + if (bitmap_get_aligned_chunk (m_nn[v], bb->index, 2) >= NN_NON_ZERO) return true; } return false; @@ -116,9 +148,8 @@ non_null_ref::adjust_range (irange &r, tree name, basic_block bb, return false; } -// Allocate an populate the bitmap for NAME. An ON bit for a block -// index indicates there is a non-null reference in that block. In -// order to populate the bitmap, a quick run of all the immediate uses +// Allocate and populate the non-null state map for NAME. +// In order to populate the bitmap, a quick run of all the immediate uses // are made and the statement checked to see if a non-null dereference // is made on that statement. @@ -139,24 +170,31 @@ non_null_ref::process_name (tree name) return; b = BITMAP_ALLOC (&m_bitmaps); + m_nn[v] = b; + + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) + return; // Loop over each immediate use and see if it implies a non-null value. FOR_EACH_IMM_USE_FAST (use_p, iter, name) { gimple *s = USE_STMT (use_p); - unsigned index = gimple_bb (s)->index; - - // If bit is already set for this block, dont bother looking again. - if (bitmap_bit_p (b, index)) + if (is_a (s)) continue; + basic_block bb = gimple_bb (s); + // If bit is already set for this block, dont bother looking again. + unsigned long val = bitmap_get_aligned_chunk (b, bb->index, 2); + unsigned long new_val; - // If we can infer a nonnull range, then set the bit for this BB - if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name) - && infer_nonnull_range (s, name)) - bitmap_set_bit (b, index); - } + // If we can infer a nonnull range, then set the bit for this BB. + if (infer_nonnull_range (s, name)) + new_val = val | NN_NON_ZERO; + else + new_val = val | NN_VARYING; - m_nn[v] = b; + if (val != new_val) + bitmap_set_aligned_chunk (b, bb->index, 2, new_val); + } } // ------------------------------------------------------------------------- diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index b54b6882aa8..2e61824593e 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -39,6 +39,8 @@ public: private: vec m_nn; void process_name (tree name); + unsigned long get_bb_state (tree name, basic_block bb); + void set_bb_state (tree name, basic_block bb, unsigned long); bitmap_obstack m_bitmaps; }; -- 2.17.2 From patchwork Mon Feb 7 14:29:45 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1589318 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=sG6qq2ms; 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 (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 RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4JspW24kRJz9s8q for ; Tue, 8 Feb 2022 01:31:58 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1F8CB385842B for ; Mon, 7 Feb 2022 14:31:56 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1F8CB385842B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1644244316; bh=6YxG+3jVq+2pBbclMv32GJkneE+P3gATqqcE6LaPK9M=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=sG6qq2msMOToGqQt61HFbXGcmK7g7wNRDquQgDpknW0dUH+L48Moak+MIsoOtKu2k b8ugEv2l5jnzEwhRP6JSO7LdSNOwHC4BcQusxBnmGumolgSkKex3KgUdIvhrMAVB61 nmqw9BXFCb3xZ7hnDRwNQs0PC7uB1IEFdW2YpCD4= 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 8F4713858C83 for ; Mon, 7 Feb 2022 14:29:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8F4713858C83 Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-164-SZrN76ELMjyS5IzRNxT5CQ-1; Mon, 07 Feb 2022 09:29:48 -0500 X-MC-Unique: SZrN76ELMjyS5IzRNxT5CQ-1 Received: by mail-qt1-f198.google.com with SMTP id x5-20020ac84d45000000b002cf826b1a18so11187629qtv.2 for ; Mon, 07 Feb 2022 06:29:48 -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:from:subject:to; bh=l5mJNFIOdexrhxEVdFgKuLQD1KHijZMD1XxpigBBmco=; b=R/43dmqyEJFPdDaEDeXgLupnbF0eauPVT2u3HH+KofQ2lgXQrPlBVmqV9RscjMYgjl tUAYe2yrJyaFTLJYrAw4hwvKbvDwGG811qdCauGVrQf8RU9hHXrrlJ1wtE3UHmrwKqYG ISNBR9YY+FS34ZrlWakXHUUTaUum7Kln6xOX34hi1B1W1ZtHuh/ZVZ4z879EKtm1sSjv OPCRfEZ3VdNLCjX9wekijfsuu1XxlXLkdnggSR6iSKTV2WkzrjL6Ye1CuT7cdqdfIJmn 8vcSVj11+X1j/MnWN8Tp539xGPjjia7eiltemNg4sabM9lskdJ6/Y7OLAjJr+co9QcrX GDTA== X-Gm-Message-State: AOAM531Voq7EUu9aTI5T7YvO08JpJfCXISnWCdD4ZGDBM51CJwGNYzqn Dx/JHMMFAi7eX5NzH5pnw1ASNi9gHtghoD1cwOdVzjdZlLFtDTb4FKCsXNtNuErGEJC9e2lqnoS Mfo0oyNV6aM+n7vyDuEd/fHG9ArgMIBUfKUktqqrVZF5kwgYSH4ps0hWNJ1w9aqKmEMGH7A== X-Received: by 2002:a05:620a:29d4:: with SMTP id s20mr6330251qkp.397.1644244187559; Mon, 07 Feb 2022 06:29:47 -0800 (PST) X-Google-Smtp-Source: ABdhPJwa5b/VA32JUPmDKkfXbz/dvJUbV5Jby0/AyNzxJAkZ7zO1UT0jKUBmzw/VaiGQbmHook14Ug== X-Received: by 2002:a05:620a:29d4:: with SMTP id s20mr6330232qkp.397.1644244187228; Mon, 07 Feb 2022 06:29:47 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id 195sm5493964qkf.30.2022.02.07.06.29.45 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Feb 2022 06:29:46 -0800 (PST) Message-ID: <53667fe7-7f67-8366-8363-ede9c3aebcb8@redhat.com> Date: Mon, 7 Feb 2022 09:29:45 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.5.1 Subject: [PATCH 2/4] tree-optimization/104288 - Register side effects during ranger vrp domwalk. To: gcc-patches , aldy Hernandez X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.1 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, 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 Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch adds the ability to register side effects within a block to ranger. This is currently only for tracking non-null values. the rvrp_folder performs a DOM walk and then attempts to simplify and the fold each stmt during the walk.  This patch adds a call to register_side_effects() to record any effects the stmt might have before returning. This checks if the non-null property is set for any ssa-names on the statement, and if they are, moves the state to only non-null for the block...  This allows us to adjust the property within the block as we do the DOM walk.  All further queries within the block will then come back as non-null.   ALl other queries will be from outside the block, so they will see the same results anyway. Unfortunately, none of the non-null routines in gimple.cc appear to work "in bulk", but rather, on a specific tree-ssa operand request at a time.  For this patch, I need to scan the entire statement looking for any operand that is nonnull (or the performance impact is awful). I took the code in the various infer_nonnull routines, and packed it all together into the two routines block_apply_nonnull && infer_nonnull_call_attributes,  which basically perform the same functionality as  infer_nonnull_range_by_dereference and infer_nonnull_range_by_attribute, only on all the operands at once.  I think its right, but you may want to have a look.   I intend to leverage this code in GCC13  for a more generalized range_after_stmt mechanism that will do away with the immediate-use visits of the current non-null This patch also has zero effect on generated code as none of the nonnull_deref_p() queries make use of the new granularity available yet.  It does set the table for the next patch. Performance impact of this is also marginal, about a 1% hit to EVRP/VRP. Bootstraps with no regressions.  OK for trunk? Andrew From c4a1e28b5b1dd8f22e7d87f34961596a816c7ad7 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 2 Feb 2022 14:44:57 -0500 Subject: [PATCH 2/3] Register side effects during ranger block walk. This patch adds the ability to register statement side effects within a block for ranger. This is currently only for tracking non-null values. * gimple-range-cache.cc (non_null_ref::try_update_to_always_nonnull): New. (non_null_ref::infer_nonnull_call_attributes): New. (non_null_loadstore): New. (non_null_ref::block_apply_nonnull): New. * gimple-range-cache.h (class non_null_ref): New prototypes. * gimple-range.cc (gimple_ranger::register_side_effects): New. * gimple-range.h (gimple_ranger::register_side_effects): New. * tree-vrp.cc (rvrp_folder::fold_stmt): Call register_side_effects. --- gcc/gimple-range-cache.cc | 106 ++++++++++++++++++++++++++++++++++++++ gcc/gimple-range-cache.h | 3 ++ gcc/gimple-range.cc | 11 ++++ gcc/gimple-range.h | 1 + gcc/tree-vrp.cc | 8 +-- 5 files changed, 126 insertions(+), 3 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 52094f0bc6a..d14dc1284f2 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -29,6 +29,10 @@ along with GCC; see the file COPYING3. If not see #include "gimple-pretty-print.h" #include "gimple-range.h" #include "tree-cfg.h" +#include "target.h" +#include "attribs.h" +#include "gimple-iterator.h" +#include "gimple-walk.h" #define DEBUG_RANGE_CACHE (dump_file \ && (param_ranger_debug & RANGER_DEBUG_CACHE)) @@ -197,6 +201,108 @@ non_null_ref::process_name (tree name) } } +// This routine will update NAME on stmt S to always_nonnull state, if it +// is in contains_nonull state. This is used during a block walk to move +// NAME to known nonnull. + +void +non_null_ref::try_update_to_always_nonnull (gimple *s, tree name) +{ + if (gimple_range_ssa_p (name) && POINTER_TYPE_P (TREE_TYPE (name))) + { + unsigned long state = get_bb_state (name, gimple_bb (s)); + // Only process when both conditions exist in the BB. + if (state != NN_BOTH) + return; + // From this point forward, we'll be NON-NULL for sure if we see one. + set_bb_state (name, gimple_bb (s), NN_NON_ZERO); + } +} + +// Adapted from infer_nonnull_range_by_attribute for calls to process +// all operands which have the nonnull attribute set in stmt. + +void +non_null_ref::infer_nonnull_call_attributes (gcall *stmt) +{ + if (gimple_call_internal_p (stmt)) + return; + + tree fntype = gimple_call_fntype (stmt); + tree attrs = TYPE_ATTRIBUTES (fntype); + for (; attrs; attrs = TREE_CHAIN (attrs)) + { + attrs = lookup_attribute ("nonnull", attrs); + + /* If "nonnull" wasn't specified, we know nothing about + the argument. */ + if (attrs == NULL_TREE) + return; + + /* Check if "nonnull" applies to all the arguments. */ + if (TREE_VALUE (attrs) == NULL_TREE) + { + for (unsigned int i = 0; i < gimple_call_num_args (stmt); i++) + { + tree op = gimple_call_arg (stmt, i); + try_update_to_always_nonnull (stmt, op); + } + return; + } + + /* Now see whats in this nonnull list. */ + for (tree t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t)) + { + unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (t)) - 1; + if (idx < gimple_call_num_args (stmt)) + { + tree op = gimple_call_arg (stmt, idx); + try_update_to_always_nonnull (stmt, op); + } + } + } +} + +// Adapted from infer_nonnull_range_by_dereference and check_loadstore +// to work for all operands. + +static bool +non_null_loadstore (gimple *s, tree op, tree, void *data) +{ + if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF) + { + /* Some address spaces may legitimately dereference zero. */ + addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op)); + if (!targetm.addr_space.zero_address_valid (as)) + { + tree ssa = TREE_OPERAND (op, 0); + ((non_null_ref *)data)->try_update_to_always_nonnull (s, ssa); + } + } + return false; +} + +// This routine is used during a block walk to move the state of non-null for +// any operands on stmt S to always nonnull. + +void +non_null_ref::block_apply_nonnull (gimple *s) +{ + if (!flag_delete_null_pointer_checks) + return; + if (is_a (s)) + return; + if (gimple_code (s) == GIMPLE_ASM || gimple_clobber_p (s)) + return; + if (is_a (s)) + { + infer_nonnull_call_attributes (as_a (s)); + return; + } + walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore, + non_null_loadstore); +} + // ------------------------------------------------------------------------- // This class represents the API into a cache of ranges for an SSA_NAME. diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 2e61824593e..0d073213226 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -36,9 +36,12 @@ public: bool non_null_deref_p (tree name, basic_block bb, bool search_dom = true); bool adjust_range (irange &r, tree name, basic_block bb, bool search_dom = true); + void block_apply_nonnull (gimple *s); + void try_update_to_always_nonnull (gimple *s, tree name); private: vec m_nn; void process_name (tree name); + void infer_nonnull_call_attributes (gcall *stmt); unsigned long get_bb_state (tree name, basic_block bb); void set_bb_state (tree name, basic_block bb, unsigned long); bitmap_obstack m_bitmaps; diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 73398ddef99..eb599d7f0d9 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -35,6 +35,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-scalar-evolution.h" #include "gimple-range.h" #include "gimple-fold.h" +#include "gimple-walk.h" gimple_ranger::gimple_ranger () : non_executable_edge_flag (cfun), @@ -436,6 +437,16 @@ gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree)) return ret; } +// Called during dominator walks to register any side effects that take effect +// from this point forward. Current release is only for tracking non-null +// within a block. + +void +gimple_ranger::register_side_effects (gimple *s) +{ + m_cache.m_non_null.block_apply_nonnull (s); +} + // This routine will export whatever global ranges are known to GCC // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index ec568153a8d..0733a534853 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -60,6 +60,7 @@ public: void dump_bb (FILE *f, basic_block bb); auto_edge_flag non_executable_edge_flag; bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree)); + void register_side_effects (gimple *s); protected: bool fold_range_internal (irange &r, gimple *s, tree name); void prefill_name (irange &r, tree name); diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index 62946450b13..e9f19d0c8b9 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -4309,9 +4309,11 @@ public: bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE { - if (m_simplifier.simplify (gsi)) - return true; - return m_ranger->fold_stmt (gsi, follow_single_use_edges); + bool ret = m_simplifier.simplify (gsi); + if (!ret) + ret = m_ranger->fold_stmt (gsi, follow_single_use_edges); + m_ranger->register_side_effects (gsi_stmt (*gsi)); + return ret; } private: -- 2.17.2 From patchwork Mon Feb 7 14:30:00 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1589323 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=f6jyKgUR; 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 4JspX71jD3z9s8q for ; Tue, 8 Feb 2022 01:32:55 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 283463858418 for ; Mon, 7 Feb 2022 14:32:53 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 283463858418 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1644244373; bh=dUDucEZCDF64bxGH6ZUomqKTd+LB32qpmZ31ZyJfYYM=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=f6jyKgURiUSL6jD71/JMmakd+ejnveIdpAlrqScu8T6UrAE2A3wJgGymxIDMUdoPb cl7JcY0+CyOonGtoDUWdEiAqjipuE2OXKPrn8G0bD43BCdptfUANcgFTRTiWFIgkjt glC9ASszNOd/U4emMJxtmQKPwiz4meEtiefmbaf8= 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 137B33858426 for ; Mon, 7 Feb 2022 14:30:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 137B33858426 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-120-dnrsW1nQNj2WEAbayCbPMg-1; Mon, 07 Feb 2022 09:30:06 -0500 X-MC-Unique: dnrsW1nQNj2WEAbayCbPMg-1 Received: by mail-qk1-f199.google.com with SMTP id bl5-20020a05620a1a8500b005088d061be4so3147178qkb.21 for ; Mon, 07 Feb 2022 06:30:06 -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:from:subject:to; bh=Fv5fXRfX8/PrC2HR+Qwo5hITStH4IFDXHkNLw8EioU0=; b=hOkvuZp2Ij3labDnhm3DPBxPz/W6FfooXWy4AyjfNVfRTjfT/Xh3jd5GiulLPSfAae JYoP/YYL0uIO1/NbVM1rQ7nbeWweEh7voeZUMKp42oKti9dMRB8Ee2vIPdj5n0NkEH1/ M4fNQMYHfNorSmefbeIIoiAlo0rIHhPyNPcMminP4Mfk2V+UPS/fz4UaECWYEDF2HAHD 30LAFo1mecL2lXRbj/32rjX/vJTbQoyTmg/tzlfEweftJoUhawMbyDhF1cOYs/rYQj+f qju+zhHcUcohlFr+4ZGPvSN9H9QiJoa952mLYOSzbO5eoigfGbanefQCbyhaCC/LrZpc B2Pw== X-Gm-Message-State: AOAM532auC77LArrAQBdWwZlaImxHItkOV9/lP6yGi2ONngk9WO96gu6 y3l1K1sGQ5LKxCJaEJi2AWvN0sjv2yUriiN+kIxd7HLkluQ/QCUlH0r4WvUqAVNFT+84ZRVBxN6 wSAKUYcNT3c5JUbE3Tr2pUnoW9iLTPYwTcemqDNuliAuRhnllj2BJ5jdtzf6jb5j1xbMIiQ== X-Received: by 2002:a05:622a:13cf:: with SMTP id p15mr7964636qtk.389.1644244205668; Mon, 07 Feb 2022 06:30:05 -0800 (PST) X-Google-Smtp-Source: ABdhPJx23kP7RToj4RNjuEYyT/qCTUhPZWrR5NQvecVgNux9+uNdk7tVQ1836vTE6E86JEUY8CcW6Q== X-Received: by 2002:a05:622a:13cf:: with SMTP id p15mr7964605qtk.389.1644244205132; Mon, 07 Feb 2022 06:30:05 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id u17sm5638904qkp.90.2022.02.07.06.30.02 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Feb 2022 06:30:02 -0800 (PST) Message-ID: <53e6de74-bd75-fe26-9473-25d27ace3c12@redhat.com> Date: Mon, 7 Feb 2022 09:30:00 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.5.1 Subject: [PATCH 3/4] tree-optimization/104288 - Update non-null interface to provide better precision. To: gcc-patches , aldy Hernandez X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-10.8 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, 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 Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This changes the non-null interface to provide more granularity and facilitate more precise queries. Previously, we could only ask if NAME was nonnull anywhere in the block, and it applied to the entire block.  now we can ask:   bool always_nonnull_p (tree name, basic_block bb);    // all uses are nonnull in the block   bool contains_nonnull_p (tree name, basic_block bb); // there is a nonnull use somewhere in the block. Ranger was using this query for on-entry and range_of_expr within block.  Range-on-entry was simply wrong.. it should have been asking if non-null was true in the dominator of this block.   And this PR demonstrate the issue with range_of_expr. This patch changes all the places which checked the state of non-null.  An Audit of every use now: ranger_cache::exit_range - Applies non-null if contains_nonnull (bb) is true ranger_cache::range_of_expr -  Applies non-null only if always_nonnull (bb). ranger_cache::fill_block_cache - marks a block to have on-entry calculated if predecessor contains_nonnull. ranger_cache::range_from_dom - Applies non-null if contains_nonnull() is true in a visited dominator block. gimple_ranger::range_of_expr - Applies non-null only if always_nonnull in the block. gimple_ranger::range_on_entry - Checks if any dominator block contains_nonnull. gimple_range::range_on_exit - Calls one of the above 2 routines, then checks if contains_nonull in this block gimple_range_path has 2 uses in range_defined_in_block() and  and adjust_for_non_null_uses.  Aldy audited both, and as the values are used at the end of the path only, so both are correct in using contains_nonull.  So there should be no impact to threading from this. This patch allows us to properly optimize: void h(int result) __attribute__((noipa)); void h(int result) {     if (result)         __builtin_exit(0); } void foo (void *p) __attribute__((nonnull(1))); void bar (void *p) {   h (p == 0);   foo (p);   if (!p)     __builtin_abort (); } to   _1 = p_3(D) == 0B;   _2 = (int) _1;   h (_2);   foo (p_3(D));   return; From a risk perspective, I don't think this patch can make us more incorrect than we were before. Oh, and compilation speed. All the patches combined with checking a little less than 1% regression overall in EVRP/VRP.  The audit exposed that the threader was invoking an unnecessary DOM lookup version of the query, and as a result, we see a 1.3% reduction in the time spent in the threader.  the overall compile time impact turned out to be a slight improvement of 0.02% overall in 380 GCC files (according to valgrind)    so its basically all good. Bootstraps with no regressions.  OK for trunk? Andrew From ba55e50356632210db368c5f7a84b3e608d21b60 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 4 Feb 2022 16:50:31 -0500 Subject: [PATCH 3/3] Update non-null interface to provide better precision. This changes the non-null interface to provide more granularity and faciltate more precise queries using the new 2 bit system. This enables the new register_side_effects code to more precisely track the non-null property. PR tree-optimization/104288 gcc/ * gimple-range-cache.cc (non_null_ref::non_null_deref_p): Delete. (non_null_ref::always_nonnull_p): New. (non_null_ref::contains_nonnull_p): New. (non_null_ref::is_nonnull_dominated_p): New. (non_null_ref::adjust_range): Delete. (non_null_ref::maybe_adjust_range: New. (ranger_cache::range_of_def): Remove call to adjust_range. (ranger_cache::entry_range): Remove call to adjust_range. (ranger_cache::exit_range): Use contains_nonnull_p. (ranger_cache::range_of_expr): Use always_nonnull_p. (ranger_cache::fill_block_cache): Call contains_nonnull_p. (ranger_cache::range_from_dom): Call contains_nonnull_p. * gimple-range-cache.h (class non_null_ref): Change prototypes. * gimple-range-path.cc (path_range_query::range_defined_in_block): Use contains_nonnull_p. (path_range_query::adjust_for_non_null_uses): Use contains_nonnull_p. * gimple-range.cc (gimple_ranger::range_of_expr): Use always_nonnull_p. (gimple_ranger::range_on_entry): Use is_nonnull_dominated_p. (gimple_ranger::range_on_exit): Use contains_nonnull_p. testsuite/gcc/ * gcc.dg/pr104288.c: New. --- gcc/gimple-range-cache.cc | 89 +++++++++++++++++++-------------- gcc/gimple-range-cache.h | 7 +-- gcc/gimple-range-path.cc | 7 +-- gcc/gimple-range.cc | 16 ++++-- gcc/testsuite/gcc.dg/pr104288.c | 23 +++++++++ 5 files changed, 94 insertions(+), 48 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr104288.c diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index d14dc1284f2..72751194c25 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -92,64 +92,79 @@ non_null_ref::set_bb_state (tree name, basic_block bb, unsigned long val) bitmap_set_aligned_chunk (m_nn[v], bb->index, 2, val); } -// Return true if NAME has a non-null dereference in block bb. If this is the -// first query for NAME, calculate the summary first. -// If SEARCH_DOM is true, the search the dominator tree as well. +// Return true if the state of NAME is always non-zero in BB. bool -non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom) +non_null_ref::always_nonnull_p (tree name, basic_block bb) +{ + if (POINTER_TYPE_P (TREE_TYPE (name)) + && get_bb_state (name, bb) == NN_NON_ZERO) + return true; + return false; +} + +// Return true if the state of NAME is non-zero at any point in BB. + +bool +non_null_ref::contains_nonnull_p (tree name, basic_block bb) +{ + if (POINTER_TYPE_P (TREE_TYPE (name)) + && get_bb_state (name, bb) >= NN_NON_ZERO) + return true; + return false; +} + +// Return true if NAME has a non-null reference in a block dominated by BB. +// If dominators are not available, simple return false. + +bool +non_null_ref::is_nonnull_dominated_p (tree name, basic_block bb) { - unsigned v = SSA_NAME_VERSION (name); if (!POINTER_TYPE_P (TREE_TYPE (name))) return false; - if (get_bb_state (name, bb) >= NN_NON_ZERO) - return true; + // Ensure the tables are allocated and available. + get_bb_state (name, bb); // See if any dominator has set non-zero. - if (search_dom && dom_info_available_p (CDI_DOMINATORS)) + if (dom_info_available_p (CDI_DOMINATORS)) { // Search back to the Def block, or the top, whichever is closer. + // As long as it is non-zero somewhere in a pred block, its nonzero here. + unsigned v = SSA_NAME_VERSION (name); basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + gcc_checking_assert (bb && def_bb != bb); basic_block def_dom = def_bb ? get_immediate_dominator (CDI_DOMINATORS, def_bb) : NULL; - for ( ; - bb && bb != def_dom; - bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + for (bb = get_immediate_dominator (CDI_DOMINATORS, bb); + bb && bb != def_dom; + bb = get_immediate_dominator (CDI_DOMINATORS, bb)) if (bitmap_get_aligned_chunk (m_nn[v], bb->index, 2) >= NN_NON_ZERO) return true; } return false; } -// If NAME has a non-null dereference in block BB, adjust R with the -// non-zero information from non_null_deref_p, and return TRUE. If -// SEARCH_DOM is true, non_null_deref_p should search the dominator tree. +// If the range of R is not already non-null, and we are allowing non-null +// ranges to be adjusted, then remove 0 from the range and return TRUE. bool -non_null_ref::adjust_range (irange &r, tree name, basic_block bb, - bool search_dom) +non_null_ref::maybe_adjust_range (irange &r) { // Non-call exceptions mean we could throw in the middle of the // block, so just punt on those for now. if (cfun->can_throw_non_call_exceptions) return false; - // We only care about the null / non-null property of pointers. - if (!POINTER_TYPE_P (TREE_TYPE (name))) - return false; - if (r.undefined_p () || r.lower_bound () != 0 || r.upper_bound () == 0) + if (r.undefined_p () || !POINTER_TYPE_P (r.type ()) + || r.lower_bound () != 0 || r.upper_bound () == 0) return false; - // Check if pointers have any non-null dereferences. - if (non_null_deref_p (name, bb, search_dom)) - { - // Remove zero from the range. - unsigned prec = TYPE_PRECISION (TREE_TYPE (name)); - r.intersect (wi::one (prec), wi::max_value (prec, UNSIGNED)); - return true; - } - return false; + + // Remove zero from the range. + unsigned prec = TYPE_PRECISION (r.type ()); + r.intersect (wi::one (prec), wi::max_value (prec, UNSIGNED)); + return true; } // Allocate and populate the non-null state map for NAME. @@ -1158,9 +1173,6 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb) else r = gimple_range_global (name); } - - if (bb) - m_non_null.adjust_range (r, name, bb, false); } // Get the range of NAME as it occurs on entry to block BB. @@ -1178,8 +1190,6 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb) // Otherwise pick up the best available global value. if (!m_on_entry.get_bb_range (r, name, bb)) range_of_def (r, name); - - m_non_null.adjust_range (r, name, bb, false); } // Get the range of NAME as it occurs on exit from block BB. @@ -1199,6 +1209,9 @@ ranger_cache::exit_range (irange &r, tree name, basic_block bb) range_of_def (r, name, bb); else entry_range (r, name, bb); + + if (m_non_null.contains_nonnull_p (name, bb)) + m_non_null.maybe_adjust_range (r); } @@ -1221,6 +1234,9 @@ ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt) range_of_def (r, name, bb); else entry_range (r, name, bb); + + if (m_non_null.always_nonnull_p (name, bb)) + m_non_null.maybe_adjust_range (r); return true; } @@ -1506,8 +1522,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // Regardless of whether we have visited pred or not, if the // pred has a non-null reference, revisit this block. - // Don't search the DOM tree. - if (m_non_null.non_null_deref_p (name, pred, false)) + if (m_non_null.contains_nonnull_p (name, pred)) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, "nonnull: update "); @@ -1582,7 +1597,7 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block bb) } // Flag if we see a non-null reference during this walk. - if (m_non_null.non_null_deref_p (name, bb, false)) + if (m_non_null.contains_nonnull_p (name, bb)) non_null = true; // If range-on-entry is set in this block, it can be used. diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 0d073213226..fc611487fad 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -33,9 +33,10 @@ class non_null_ref public: non_null_ref (); ~non_null_ref (); - bool non_null_deref_p (tree name, basic_block bb, bool search_dom = true); - bool adjust_range (irange &r, tree name, basic_block bb, - bool search_dom = true); + bool always_nonnull_p (tree name, basic_block bb); + bool contains_nonnull_p (tree name, basic_block bb); + bool is_nonnull_dominated_p (tree name, basic_block bb); + bool maybe_adjust_range (irange &r); void block_apply_nonnull (gimple *s); void try_update_to_always_nonnull (gimple *s, tree name); private: diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index 3ee4989f4b0..74ce9357fc3 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -354,8 +354,8 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb) r.set_varying (TREE_TYPE (name)); } - if (bb) - m_non_null.adjust_range (r, name, bb); + if (bb && m_non_null.contains_nonnull_p (name, bb)) + m_non_null.maybe_adjust_range (r); if (DEBUG_SOLVER && (bb || !r.varying_p ())) { @@ -525,7 +525,8 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) else r.set_varying (TREE_TYPE (name)); - if (m_non_null.adjust_range (r, name, bb)) + if (m_non_null.contains_nonnull_p (name, bb) + && m_non_null.maybe_adjust_range (r)) set_cache (r, name); } } diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index eb599d7f0d9..12961dbc971 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -117,13 +117,13 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) // If name is defined in this block, try to get an range from S. if (def_stmt && gimple_bb (def_stmt) == bb) - { - range_of_stmt (r, def_stmt, expr); - m_cache.m_non_null.adjust_range (r, expr, bb, true); - } + range_of_stmt (r, def_stmt, expr); // Otherwise OP comes from outside this block, use range on entry. else range_on_entry (r, bb, expr); + // If NAME is known to be non-null in this block, adjust the range. + if (r.varying_p () && m_cache.m_non_null.always_nonnull_p (expr, bb)) + m_cache.m_non_null.maybe_adjust_range (r); } if (idx) tracer.trailer (idx, "range_of_expr", true, expr, r); @@ -152,7 +152,9 @@ gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name) if (m_cache.block_range (entry_range, bb, name)) r.intersect (entry_range); - m_cache.m_non_null.adjust_range (r, name, bb, true); + // Pick up any nonnull info from the dominating predecessor. + if (r.varying_p () && m_cache.m_non_null.is_nonnull_dominated_p (name, bb)) + m_cache.m_non_null.maybe_adjust_range (r); if (idx) tracer.trailer (idx, "range_on_entry", true, name, r); @@ -186,6 +188,10 @@ gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name) range_of_expr (r, name, s); else range_on_entry (r, bb, name); + + if (r.varying_p () && m_cache.m_non_null.contains_nonnull_p (name, bb)) + m_cache.m_non_null.maybe_adjust_range (r); + gcc_checking_assert (r.undefined_p () || range_compatible_p (r.type (), TREE_TYPE (name))); diff --git a/gcc/testsuite/gcc.dg/pr104288.c b/gcc/testsuite/gcc.dg/pr104288.c new file mode 100644 index 00000000000..95eb196f9e4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr104288.c @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp -fdelete-null-pointer-checks" } */ +/* { dg-skip-if "" { keeps_null_pointer_checks } } */ + +void keep(int result) __attribute__((noipa)); +void keep(int result) +{ + if (result) + __builtin_exit(0); +} + +void foo (void *p) __attribute__((nonnull(1))); + +void bar (void *p) +{ + keep (p == 0); + foo (p); + if (!p) + __builtin_abort (); +} + +/* { dg-final { scan-tree-dump-not "abort" "evrp" } } */ +/* { dg-final { scan-tree-dump-times "== 0B;" 1 "evrp" } } */ -- 2.17.2 From patchwork Mon Feb 7 14:30:21 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1589325 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=MS+CJnxQ; 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 4JspYM05y3z9s8q for ; Tue, 8 Feb 2022 01:33:59 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E4E42385841C for ; Mon, 7 Feb 2022 14:33:56 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E4E42385841C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1644244436; bh=te27PnAZp2/Ht3zF4DBfT/T6/MSnm+bl4SvlWz623RM=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=MS+CJnxQau8QA6dePREx3E2c3sBRa+Yq+W1ltFjWLx1RqM6Yp/gxkXQ6Y1N+XY23k tvi/QjUphrR817UEh6JwetclHp8sazdHsYaNX0Z7zlV5rdJcdNA9VsSmUY1p7YU2mR gBBR/wBedyFEcUp8UCY+PR1sIF9fse6lqqWI7W/w= 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 5F46B3858430 for ; Mon, 7 Feb 2022 14:30:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5F46B3858430 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-510-BY3pwtafNeaZNZm9aUPfFw-1; Mon, 07 Feb 2022 09:30:24 -0500 X-MC-Unique: BY3pwtafNeaZNZm9aUPfFw-1 Received: by mail-qk1-f200.google.com with SMTP id p23-20020a05620a15f700b00506d8ec3749so8722657qkm.4 for ; Mon, 07 Feb 2022 06:30:24 -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:from:subject:to; bh=kjNgLbCZcqqDVXJMtI4M/uOnfGfWT0l1xdgwklvGK1Y=; b=htpiOrFdKx6AQBaiVVdijKX0xHjBXaVjtklooAHnGqTDzRdYXiQFlXGeg32wdUtTTY NwG5SYJNFJmRioFFROgFGUOG0ZZH5PR78Iwek7xJOC1+XMJ4z9Fwo/xjFDJxyfiuEhA0 NC9uadfs6VCdpBagpVS43XUbsFLXN2WuCadoW1gHJRrnilDzSSt1cQB9fvpg1EWpdooU c+wuQNEfI6P3rFmotIzYr57VjYxG+VPL7dTDqTaIWemvPNwrgQdNl42ZxoGEBwRgJdnb NKzY/MONHUm+FkNCE1OAblQtAw+uXqCIVW9bLEPyAI0mkHQcEpp72mhukDudiMCyqScq xbLw== X-Gm-Message-State: AOAM5303ywOBHWpcsg42LmVVyRzm25VB2F19YRuKd29cF12Lxu+6WHub WNVJjPc1G+K9Q60dWsPP7r8QGSF3s2liN32ndDwQkp876cnYXaeTHTRziMdRpqDxI36isbcJc7Y BgFHL1Yp+AVyO1qbO8h+MFiyGIEygtLofCrf5GrE7EPHwal2pQjF7Pu4oeJJM4KFXKzBpug== X-Received: by 2002:a37:6791:: with SMTP id b139mr6273322qkc.765.1644244223287; Mon, 07 Feb 2022 06:30:23 -0800 (PST) X-Google-Smtp-Source: ABdhPJyVWym9rqVf38Z/aP/MCNkRoZqjjg6I0WaWC0xbLpF5aHECmAwwKn3zpSEJ44OPLtGeOUfnLA== X-Received: by 2002:a37:6791:: with SMTP id b139mr6273306qkc.765.1644244223025; Mon, 07 Feb 2022 06:30:23 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id u6sm5480456qki.136.2022.02.07.06.30.21 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Feb 2022 06:30:22 -0800 (PST) Message-ID: Date: Mon, 7 Feb 2022 09:30:21 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.5.1 Subject: [PATCH 4/4] [GCC11] tree-optimization/104288 - range on entry should check dominators for non-null. To: gcc-patches , Aldy Hernandez X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA 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, RCVD_IN_DNSWL_LOW, 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 Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" The patches resolves the issue for GCC11 in a much simpler way. By default, ranger and EVRP are running in hybrid mode. This means if ranger misses something, evrp will pick up the slack. This enables us to change the 2 places which check for non-null to ignore potentially incorrect block-wide information and only query dominator blocks for on-entry ranges.  This allows ranger to be conservative, and EVRP will pick up the intra-block changes. Bootstraps with no regressions.  OK for gcc 11 branch? From b807249b310153349a2593203eba44c456b6208e Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 31 Jan 2022 11:37:16 -0500 Subject: [PATCH] Range on entry should only check dominators for non-null. Range-on-entry checks should no check the state of non-null within the current block. If dominators are present, use the dominator. PR tree-optimization/104288 gcc/ * gimple-range-cache.cc (ssa_range_in_bb): Only use non-null from the dominator entry ranges. * gimple-range.cc (gimple_ranger::range_of_expr): Ditto. gcc/testsuite/ * gcc.dg/pr104288.c: New. --- gcc/gimple-range-cache.cc | 19 ++++++++++++------- gcc/gimple-range.cc | 16 ++++++++++------ gcc/testsuite/gcc.dg/pr104288.c | 23 +++++++++++++++++++++++ 3 files changed, 45 insertions(+), 13 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr104288.c diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 6ddeca3766d..b05b804d513 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -905,14 +905,19 @@ ranger_cache::ssa_range_in_bb (irange &r, tree name, basic_block bb) // Try to pick up any known global value as a best guess for now. if (!m_globals.get_global_range (r, name)) r = gimple_range_global (name); + // Check for non-null on entry if dominators are available by + // resetting def_bb to the block we want to search. + if (dom_info_available_p (CDI_DOMINATORS)) + { + basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); + // Check if pointers have any non-null dereferences. Non-call + // exceptions mean we could throw in the middle of the block, so just + // punt for now on those. + if (dom_bb && r.varying_p () && !cfun->can_throw_non_call_exceptions + && m_non_null.non_null_deref_p (name, dom_bb)) + r = range_nonzero (TREE_TYPE (name)); + } } - - // Check if pointers have any non-null dereferences. Non-call - // exceptions mean we could throw in the middle of the block, so just - // punt for now on those. - if (r.varying_p () && m_non_null.non_null_deref_p (name, bb) && - !cfun->can_throw_non_call_exceptions) - r = range_nonzero (TREE_TYPE (name)); } // Return a static range for NAME on entry to basic block BB in R. If diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index f861459ed96..42c637458ad 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -979,10 +979,14 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) // If name is defined in this block, try to get an range from S. if (def_stmt && gimple_bb (def_stmt) == bb) - range_of_stmt (r, def_stmt, expr); - else - // Otherwise OP comes from outside this block, use range on entry. - range_on_entry (r, bb, expr); + return range_of_stmt (r, def_stmt, expr); + + // Otherwise OP comes from outside this block, use range on entry. + range_on_entry (r, bb, expr); + // Check for non-null in the predecessor if dominators are available. + if (!dom_info_available_p (CDI_DOMINATORS)) + return true; + basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); // No range yet, see if there is a dereference in the block. // We don't care if it's between the def and a use within a block @@ -992,8 +996,8 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) // in which case we may need to walk from S back to the def/top of block // to make sure the deref happens between S and there before claiming // there is a deref. Punt for now. - if (!cfun->can_throw_non_call_exceptions && r.varying_p () && - m_cache.m_non_null.non_null_deref_p (expr, bb)) + if (dom_bb && !cfun->can_throw_non_call_exceptions && r.varying_p () + && m_cache.m_non_null.non_null_deref_p (expr, dom_bb)) r = range_nonzero (TREE_TYPE (expr)); return true; diff --git a/gcc/testsuite/gcc.dg/pr104288.c b/gcc/testsuite/gcc.dg/pr104288.c new file mode 100644 index 00000000000..95eb196f9e4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr104288.c @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp -fdelete-null-pointer-checks" } */ +/* { dg-skip-if "" { keeps_null_pointer_checks } } */ + +void keep(int result) __attribute__((noipa)); +void keep(int result) +{ + if (result) + __builtin_exit(0); +} + +void foo (void *p) __attribute__((nonnull(1))); + +void bar (void *p) +{ + keep (p == 0); + foo (p); + if (!p) + __builtin_abort (); +} + +/* { dg-final { scan-tree-dump-not "abort" "evrp" } } */ +/* { dg-final { scan-tree-dump-times "== 0B;" 1 "evrp" } } */ -- 2.17.2 From patchwork Tue Feb 8 01:33:14 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1589652 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=wGTb+HWa; 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 4Jt5C14jpPz9sFn for ; Tue, 8 Feb 2022 12:34:04 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9A814385840C for ; Tue, 8 Feb 2022 01:34:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9A814385840C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1644284041; bh=k0Jzzm9cR6xxUjc8u9Z6/G3mfDKaV+DjS4+oApuvUJk=; h=Date:Subject:To:References:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=wGTb+HWaVp0WwbCQ72B3EoEF7poXut0XaLMO+HzCAtk24WNb4Y+BUjAlEYAIh1ck9 181MtovYWEk3Q8OLO2R/rdFJyaBZ6jst/U8AYbJch6M8rZa2XfYjOxay/UwRLr1ddR BSmm7RJ2mP3zqJmWfo6m14JY2fFnURrPe+RbU8GI= 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 1AB3B3858C83 for ; Tue, 8 Feb 2022 01:33:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1AB3B3858C83 Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-267-4UGrWgUvN--FD7ZBXLiYcA-1; Mon, 07 Feb 2022 20:33:17 -0500 X-MC-Unique: 4UGrWgUvN--FD7ZBXLiYcA-1 Received: by mail-qv1-f70.google.com with SMTP id ge15-20020a05621427cf00b00421df9f8f23so9813447qvb.17 for ; Mon, 07 Feb 2022 17:33:17 -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:subject :content-language:from:to:references:in-reply-to; bh=+AS1ArrXaCNYZgInV6D7K75zIaYyhA731Lc74V5ends=; b=b9WAY6YIi1upqKVeTgGUQEI+MzdQgVCMUAnpkDlc+nU5tgJY4P8yhKvvfFGDGSdcjv 9oR2jEsSHudzNGelTqlfZrgGe9REUp7fpLQoA3I681uqs73Yb4RQTQ5K2nhOC/MXMly+ TCB1lv7rEUn87U2LiSCcXc6RgOsTT/dLJTzib1q76N/SluDc9+y6G8/vGPEQiPnSdOWU a+xDWEL2AFxMGOPsbDPWvUKEPeP6amXa/Nwmezn45N2FOrFPDL9WYRlEfhSEy1Llf/bV +qx8U4vCw6obp8jK1mWWpKTVdi1W6UfFzBEN6uBENGoQupr/isXPFBNjzb1TMXvcz8Ig lBtg== X-Gm-Message-State: AOAM53247LKo2VlCHarXUqgklkntsqVy5GseIQYkQhnt+XlbQ/8pL9i4 bSlKEwEYocruQF2MkoladSz7pYiFhywl0vymWbwqoxDg6aYQhIJoHo0oGmmDNBx5V1sELp7mFuP a+3pIXeCMC83uvsjfX3inmjSwP49X1Drxo+unquvsSwFdRqnVOSgaq/hskZmA2+hbZ1P8NQ== X-Received: by 2002:ac8:5a83:: with SMTP id c3mr1599790qtc.51.1644283996482; Mon, 07 Feb 2022 17:33:16 -0800 (PST) X-Google-Smtp-Source: ABdhPJwFUfClfpEuoqSihlN8Hl4CJh5qk6aMc3PDjX9shP8YgU4fL1NAi6ZUFix3xbnpUW62kaDbnA== X-Received: by 2002:ac8:5a83:: with SMTP id c3mr1599777qtc.51.1644283996209; Mon, 07 Feb 2022 17:33:16 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id j11sm6552488qtx.67.2022.02.07.17.33.15 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 07 Feb 2022 17:33:15 -0800 (PST) Message-ID: Date: Mon, 7 Feb 2022 20:33:14 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.5.1 Subject: [PATCH 5/4] tree-optimization/104288 - An alternative approach To: gcc-patches , Aldy Hernandez References: <4425f569-b42a-bd10-b3c7-bc110e9a5c95@redhat.com> In-Reply-To: <4425f569-b42a-bd10-b3c7-bc110e9a5c95@redhat.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.5 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, 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 Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" On 2/7/22 09:29, Andrew MacLeod wrote: > I have a proposal for PR 104288. > > ALL patches (in sequence) bootstrap on their own and each cause no > regressions. I've been continuing to work with this towards the GCC13 solution for statement side effects.  And There is another possibility we could pursue which is less intrusive I adapted the portions of patch 2/4 which process nonnull, but changes it from being in the nonnull class to being in the cache. THe main difference is it continues to use a single bit, just changing all uses of it to *always* mean its non-null on exit to the block. Range-on-entry is changed to only check dominator blocks, and range_of_expr doesn't check the bit at all.. in both ranger and the cache. When we are doing the block walk and process side effects, the on-entry *cache* range for the block is adjusted to be non-null instead.   The statements which precede this stmt have already been processed, and all remaining statements in this block will now pick up this new non-value from the on-entry cache.  This should be perfectly safe. The final tweak is when range_of_expr is looking the def block, it normally does not have an on entry cache value.  (the def is in the block, so there is no entry cache value).  It now checks to see if we have set one, which can only happen when we have been doing the statement walk and set the on-entry cache with  a non-null value.  This allows us to pick up the non-null range in the def block too... (once we have passed a statement which set nonnull of course). THis patch provides much less change to trunk, and is probably a better approach as its closer to what is going to happen in GCC13. Im still working with it, so the patch isnt fully refined yet... but it bootstraps and passes all test with no regressions.  And passes the new tests too.   I figured I would mention this before you look to hard at the other patchset.    the GCC11 patch doesn't change. Let me know if you prefer this.... I think I do :-)  less churn, and closer to end state. Andrew commit da6185993cf85f38b08e4c2801ca8e5fe914e40d Author: Andrew MacLeod Date: Mon Feb 7 15:52:16 2022 -0500 Change nonnull to mean nonnull at exit. * gimple-range-cache.cc (non_null_ref::set_nonnull): New. (ranger_cache::range_of_def): Don't check non-null. (ranger_cache::entry_range): Don't check non-null. (ranger_cache::try_update_to_always_nonnull): New. (ranger_cache::infer_nonnull_call_attributes): New. (non_null_loadstore): New. (ranger_cache::block_apply_nonnull): New. * ranger-cache.h (class non_null_ref): Update prototypes. (class ranger_cache): Update prototypes. * gimple-range-path.cc (path_range_query::range_defined_in_block): Do not search dominators. (path_range_query::adjust_for_non_null_uses): Ditto. * gimple-range.cc (gimple_ranger::range_of_expr): Check on-entry for def overrides. Do not check nonnull. (gimple_ranger::range_on_entry): Check dominators for nonnull. (gimple_ranger::range_on_exit): Check for nonnull. * gimple-range.cc (gimple_ranger::register_side_effects): New. * gimple-range.h (gimple_ranger::register_side_effects): New. * tree-vrp.cc (rvrp_folder::fold_stmt): Call register_side_effects. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 16c881b13e1..c6aefb98b42 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -29,6 +29,10 @@ along with GCC; see the file COPYING3. If not see #include "gimple-pretty-print.h" #include "gimple-range.h" #include "tree-cfg.h" +#include "target.h" +#include "attribs.h" +#include "gimple-iterator.h" +#include "gimple-walk.h" #define DEBUG_RANGE_CACHE (dump_file \ && (param_ranger_debug & RANGER_DEBUG_CACHE)) @@ -50,6 +54,22 @@ non_null_ref::~non_null_ref () m_nn.release (); } +// This routine will update NAME in BB to be nonnull if it is not already. +// return TRUE if the update happens., + +bool +non_null_ref::set_nonnull (basic_block bb, tree name) +{ + gcc_checking_assert (gimple_range_ssa_p (name) + && POINTER_TYPE_P (TREE_TYPE (name))); + // Only process when its not already set. + if (non_null_deref_p (name, bb, false)) + return false; + // From this point forward, we'll be NON-NULL for sure if we see one. + bitmap_set_bit (m_nn[SSA_NAME_VERSION (name)], bb->index); + return true; +} + // Return true if NAME has a non-null dereference in block bb. If this is the // first query for NAME, calculate the summary first. // If SEARCH_DOM is true, the search the dominator tree as well. @@ -1014,9 +1034,6 @@ ranger_cache::range_of_def (irange &r, tree name, basic_block bb) else r = gimple_range_global (name); } - - if (bb) - m_non_null.adjust_range (r, name, bb, false); } // Get the range of NAME as it occurs on entry to block BB. @@ -1034,8 +1051,6 @@ ranger_cache::entry_range (irange &r, tree name, basic_block bb) // Otherwise pick up the best available global value. if (!m_on_entry.get_bb_range (r, name, bb)) range_of_def (r, name); - - m_non_null.adjust_range (r, name, bb, false); } // Get the range of NAME as it occurs on exit from block BB. @@ -1467,3 +1482,107 @@ ranger_cache::range_from_dom (irange &r, tree name, basic_block bb) } return true; } + +// This routine will update NAME in block BB to the nonnull state. +// It will then update the on-netry cache for this block to be non-null +// if it isn't already. + +void +ranger_cache::try_update_to_always_nonnull (basic_block bb, tree name) +{ + if (gimple_range_ssa_p (name) && POINTER_TYPE_P (TREE_TYPE (name))) + { + m_non_null.set_nonnull (bb, name); + // Update the on-entry cache for BB to be non-zero + int_range_max r; + exit_range (r, name, bb); + if (m_non_null.adjust_range (r, name, bb, false)) + m_on_entry.set_bb_range (name, bb, r); + } +} + +// Adapted from infer_nonnull_range_by_attribute for calls to process +// all operands which have the nonnull attribute set in stmt. + +void +ranger_cache::infer_nonnull_call_attributes (gcall *stmt) +{ + if (gimple_call_internal_p (stmt)) + return; + + basic_block bb = gimple_bb (stmt); + tree fntype = gimple_call_fntype (stmt); + tree attrs = TYPE_ATTRIBUTES (fntype); + for (; attrs; attrs = TREE_CHAIN (attrs)) + { + attrs = lookup_attribute ("nonnull", attrs); + + /* If "nonnull" wasn't specified, we know nothing about + the argument. */ + if (attrs == NULL_TREE) + return; + + /* Check if "nonnull" applies to all the arguments. */ + if (TREE_VALUE (attrs) == NULL_TREE) + { + for (unsigned int i = 0; i < gimple_call_num_args (stmt); i++) + { + tree op = gimple_call_arg (stmt, i); + try_update_to_always_nonnull (bb, op); + } + return; + } + + /* Now see whats in this nonnull list. */ + for (tree t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t)) + { + unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (t)) - 1; + if (idx < gimple_call_num_args (stmt)) + { + tree op = gimple_call_arg (stmt, idx); + try_update_to_always_nonnull (bb, op); + } + } + } +} + +// Adapted from infer_nonnull_range_by_dereference and check_loadstore +// to work for all operands. + +static bool +non_null_loadstore (gimple *s, tree op, tree, void *data) +{ + if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF) + { + /* Some address spaces may legitimately dereference zero. */ + addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op)); + if (!targetm.addr_space.zero_address_valid (as)) + { + tree ssa = TREE_OPERAND (op, 0); + basic_block bb = gimple_bb (s); + ((ranger_cache *)data)->try_update_to_always_nonnull (bb, ssa); + } + } + return false; +} + +// This routine is used during a block walk to move the state of non-null for +// any operands on stmt S to always nonnull. + +void +ranger_cache::block_apply_nonnull (gimple *s) +{ + if (!flag_delete_null_pointer_checks) + return; + if (is_a (s)) + return; + if (gimple_code (s) == GIMPLE_ASM || gimple_clobber_p (s)) + return; + if (is_a (s)) + { + infer_nonnull_call_attributes (as_a (s)); + return; + } + walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore, + non_null_loadstore); +} diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index b54b6882aa8..f189fd8898f 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -36,6 +36,7 @@ public: bool non_null_deref_p (tree name, basic_block bb, bool search_dom = true); bool adjust_range (irange &r, tree name, basic_block bb, bool search_dom = true); + bool set_nonnull (basic_block bb, tree name); private: vec m_nn; void process_name (tree name); @@ -106,6 +107,8 @@ public: void propagate_updated_value (tree name, basic_block bb); + void block_apply_nonnull (gimple *s); + void try_update_to_always_nonnull (basic_block bb, tree name); non_null_ref m_non_null; gori_compute m_gori; @@ -118,6 +121,8 @@ private: void fill_block_cache (tree name, basic_block bb, basic_block def_bb); void propagate_cache (tree name); + void infer_nonnull_call_attributes (gcall *stmt); + void range_of_def (irange &r, tree name, basic_block bb = NULL); void entry_range (irange &r, tree expr, basic_block bb); void exit_range (irange &r, tree expr, basic_block bb); diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index 3bf9bd1e981..483bcd2e582 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -358,7 +358,7 @@ path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb) } if (bb) - m_non_null.adjust_range (r, name, bb); + m_non_null.adjust_range (r, name, bb, false); if (DEBUG_SOLVER && (bb || !r.varying_p ())) { @@ -528,7 +528,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) else r.set_varying (TREE_TYPE (name)); - if (m_non_null.adjust_range (r, name, bb)) + if (m_non_null.adjust_range (r, name, bb, false)) set_cache (r, name); } } diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 73398ddef99..bffda11a558 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -35,6 +35,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-scalar-evolution.h" #include "gimple-range.h" #include "gimple-fold.h" +#include "gimple-walk.h" gimple_ranger::gimple_ranger () : non_executable_edge_flag (cfun), @@ -117,8 +118,9 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) // If name is defined in this block, try to get an range from S. if (def_stmt && gimple_bb (def_stmt) == bb) { - range_of_stmt (r, def_stmt, expr); - m_cache.m_non_null.adjust_range (r, expr, bb, true); + // Check for a defintion override from a block walk. + if (!m_cache.block_range (r, bb, expr, false)) + range_of_stmt (r, def_stmt, expr); } // Otherwise OP comes from outside this block, use range on entry. else @@ -151,7 +153,12 @@ gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name) if (m_cache.block_range (entry_range, bb, name)) r.intersect (entry_range); - m_cache.m_non_null.adjust_range (r, name, bb, true); + if (dom_info_available_p (CDI_DOMINATORS)) + { + basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); + if (dom_bb) + m_cache.m_non_null.adjust_range (r, name, dom_bb, true); + } if (idx) tracer.trailer (idx, "range_on_entry", true, name, r); @@ -185,6 +192,7 @@ gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name) range_of_expr (r, name, s); else range_on_entry (r, bb, name); + m_cache.m_non_null.adjust_range (r, name, bb, false); gcc_checking_assert (r.undefined_p () || range_compatible_p (r.type (), TREE_TYPE (name))); @@ -436,6 +444,16 @@ gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree)) return ret; } +// Called during dominator walks to register any side effects that take effect +// from this point forward. Current release is only for tracking non-null +// within a block. + +void +gimple_ranger::register_side_effects (gimple *s) +{ + m_cache.block_apply_nonnull (s); +} + // This routine will export whatever global ranges are known to GCC // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index ec568153a8d..0733a534853 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -60,6 +60,7 @@ public: void dump_bb (FILE *f, basic_block bb); auto_edge_flag non_executable_edge_flag; bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree)); + void register_side_effects (gimple *s); protected: bool fold_range_internal (irange &r, gimple *s, tree name); void prefill_name (irange &r, tree name); diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc index 62946450b13..e9f19d0c8b9 100644 --- a/gcc/tree-vrp.cc +++ b/gcc/tree-vrp.cc @@ -4309,9 +4309,11 @@ public: bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE { - if (m_simplifier.simplify (gsi)) - return true; - return m_ranger->fold_stmt (gsi, follow_single_use_edges); + bool ret = m_simplifier.simplify (gsi); + if (!ret) + ret = m_ranger->fold_stmt (gsi, follow_single_use_edges); + m_ranger->register_side_effects (gsi_stmt (*gsi)); + return ret; } private: