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: 50861 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2234C3858431 for ; Mon, 7 Feb 2022 14:33:02 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2234C3858431 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1644244382; bh=dUDucEZCDF64bxGH6ZUomqKTd+LB32qpmZ31ZyJfYYM=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=JdWv6vpu9bzLnl2PQPKYF+Lm4cKqkPUAOreBlEFnKZj08prZI5Ei1Uik5+wd1yquE mgxqDBLtHWgU0Ld/NBbqHpSwC+sX34qwChJDwOvzTL6/hezLGmyYDmQOrGdn1ZEIPL B5iALi1aDv2oIqsTGUXQh1zlBEyNjZuZtoGWPzUA= 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+patchwork=sourceware.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