From patchwork Fri May 7 19:03:56 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1475654 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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@gcc.gnu.org; receiver=) Authentication-Results: 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=BOyemTbb; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4FcKcQ0Fpnz9t2b for ; Sat, 8 May 2021 05:04:05 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D2DDC385383B; Fri, 7 May 2021 19:04:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D2DDC385383B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1620414243; bh=AMJCJe6HpiblufTteLo5OdbwngtUHZnkPb7gXArpxhU=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=BOyemTbbJJeQbsb3wn0J66t/bqL06ZgpbyqnTqHB4Csalzli6xdB5MRXX0jxPpSEU C9eu2lBNIJPcTdKb5+eemPtSVCDzjwks57m4POKpgxhp+DbcGCQfqZxZUbJWSIjMIY sAg/xJ/xwihS2H/H/XzbvBo2HEIbPEoHz0QC5Cvo= 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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 2CFD1385383B for ; Fri, 7 May 2021 19:04:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 2CFD1385383B Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-73-6Q7d2KRAObe3aezJWbvqCA-1; Fri, 07 May 2021 15:03:58 -0400 X-MC-Unique: 6Q7d2KRAObe3aezJWbvqCA-1 Received: by mail-qv1-f70.google.com with SMTP id l5-20020a0ce0850000b02901c37c281207so7325355qvk.11 for ; Fri, 07 May 2021 12:03:58 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:from:subject:cc:message-id:date:user-agent :mime-version:content-language; bh=AMJCJe6HpiblufTteLo5OdbwngtUHZnkPb7gXArpxhU=; b=Y7Wwj1gG6x81r1mi3mTAFmgS89KzpGbnWuHGf8wMFLE5C7q6EdssA1ae24xQUOixqz ZF2wC5Fr/tBKqpmUraLXRru5TORSTUWWY2rZA6fGYrjRZxS5gA6Jt4SZrJ3qh9Y5os2p 7UPYnQD3H/fXLfyTeEqgEKa9UD+ObYAqLh3Qii7GIfxMe3M0oI3NuGRTh9WFOYVqzMYH Q/sgr2fU5NgxnGDKdSOT9MQ/w8EbqzfSDn4PreBOXmYdiwu5ZWGhCe41qMiQG0FvdDcO obxFoq6ApJPUkFmvn9lOJx82EW5X7L58EAZHaqY3n0MOkQuwYqmxNkUp3KlyUiFRnxEf WXhQ== X-Gm-Message-State: AOAM531fAa1QZsxcd7B0qBtiH0r4FQPFmCB9qn/NJSf2WYLRSuWNHtI0 n0p6Au28Iu9DCf4Bm+lHicXslOZZOik8tlf0oG8dFxkAJv2NYUSlE+bRnkI9JfofVoVD2GSXkvp QhArXysfUgcTrqweoew== X-Received: by 2002:ad4:5aa1:: with SMTP id u1mr11234479qvg.23.1620414237694; Fri, 07 May 2021 12:03:57 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzcwMRK+hMDS6P9ZRVMjOoIILLjqhtRvP6TgE2emiWTv9Pj37I+Kq4+vAL1g+qbo644nCEj4Q== X-Received: by 2002:ad4:5aa1:: with SMTP id u1mr11234461qvg.23.1620414237564; Fri, 07 May 2021 12:03:57 -0700 (PDT) Received: from ?IPv6:2607:fea8:a25f:fa00:6ae8:97ac:cf69:b86d? ([2607:fea8:a25f:fa00:6ae8:97ac:cf69:b86d]) by smtp.gmail.com with ESMTPSA id f2sm5614203qkh.76.2021.05.07.12.03.56 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 07 May 2021 12:03:57 -0700 (PDT) To: gcc-patches Subject: [PATCH] Use the dominator tree when checking for non-null. Message-ID: <9d09140b-ac84-b868-7798-d9e1dd958dfb@redhat.com> Date: Fri, 7 May 2021 15:03:56 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.9.1 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.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, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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@gcc.gnu.org Sender: "Gcc-patches" The current non-null processing only sets a bit for the block which contains a non-null setting event. We should check the dom tree to see if a predecessor dom block sets non-null, otherwise we can miss it.  We don't need to do this within the propagation engines like the on-entry cache.  They will propagate the range as appropriate without looking at the dom tree. So it just as the client level query this is needed, make it the default. Later, the non-null processing will be replaced, but at least get it right for now. Bootstraps on  x86_64-pc-linux-gnu with no testsuite regressions. Pushed. Andrew commit 37935ca2f4b5a89322a24620fbec3f3c9f2845fd Author: Andrew MacLeod Date: Tue Apr 27 08:44:46 2021 -0400 When searching for non-null, check the dominator tree. The non-null bitmap only indicates which blocks non-null setting occurs. Generalized queries need to search the dom tree, whereas propagation engines only need to know the current block. Add a flag for this purpose. * gimple-range-cache.cc (non_null_ref::non_null_deref_p): Search dominator tree is available and requested. (ranger_cache::ssa_range_in_bb): Don't search dom tree here. (ranger_cache::fill_block_cache): Don't search dom tree here either. * gimple-range-cache.h (non_null_deref_p): Add dom_search param. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 38e4fe1c7c0..9b401927bd6 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -48,9 +48,10 @@ non_null_ref::~non_null_ref () // 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) +non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom) { if (!POINTER_TYPE_P (TREE_TYPE (name))) return false; @@ -59,7 +60,24 @@ non_null_ref::non_null_deref_p (tree name, basic_block bb) if (!m_nn[v]) process_name (name); - return bitmap_bit_p (m_nn[v], bb->index); + if (bitmap_bit_p (m_nn[v], bb->index)) + return true; + + // See if any dominator has set non-zero. + if (search_dom && dom_info_available_p (CDI_DOMINATORS)) + { + // Search back to the Def block, or the top, whichever is closer. + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + 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)) + if (bitmap_bit_p (m_nn[v], bb->index)) + return true; + } + return false; } // Allocate an populate the bitmap for NAME. An ON bit for a block @@ -800,7 +818,7 @@ ranger_cache::ssa_range_in_bb (irange &r, tree name, basic_block 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 (r.varying_p () && m_non_null.non_null_deref_p (name, bb) && + if (r.varying_p () && m_non_null.non_null_deref_p (name, bb, false) && !cfun->can_throw_non_call_exceptions) r = range_nonzero (TREE_TYPE (name)); } @@ -1066,7 +1084,8 @@ 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. - if (m_non_null.non_null_deref_p (name, pred)) + // Don't search the DOM tree. + if (m_non_null.non_null_deref_p (name, pred, false)) { if (DEBUG_RANGE_CACHE) fprintf (dump_file, "nonnull: update "); diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 2b36a02654b..986a68a9e06 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -33,7 +33,7 @@ class non_null_ref public: non_null_ref (); ~non_null_ref (); - bool non_null_deref_p (tree name, basic_block bb); + bool non_null_deref_p (tree name, basic_block bb, bool search_dom = true); private: vec m_nn; void process_name (tree name);