From patchwork Fri Dec 3 20:39:59 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 48481 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 BC12A385840D for ; Fri, 3 Dec 2021 20:41:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BC12A385840D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638564119; bh=mDjr6oLe/o0QYMKd4kBCch4/gpmwEKWY3AKO62BIbU0=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=GytMuWZpHw3gAFH8MgD/mR58yXluiBwTxW9kjUXHeqIUJ7NaOVD5RZfXDs+HMtZ9B dyLpJ3mWTlP5ZPcJh3EEIkQImPMT6U039rB4/wmVTxEEGHobO9CUYaIuVKH1DDKbOC Rloi6R4hRYaJzUcaqjYr+006e3iZ51YbGd+yXpog= 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 992223858420 for ; Fri, 3 Dec 2021 20:40:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 992223858420 Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-393-jcmwRrJwMnqYC3-aRIOJAw-1; Fri, 03 Dec 2021 15:40:03 -0500 X-MC-Unique: jcmwRrJwMnqYC3-aRIOJAw-1 Received: by mail-qt1-f200.google.com with SMTP id o12-20020a05622a008c00b002aff5552c89so4822734qtw.23 for ; Fri, 03 Dec 2021 12:40:03 -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:to:from:subject:cc; bh=miAvP2CO+5Wt+slPDAe5kX+SJegdNpTnNeT+czzR1+c=; b=BorgHHyavjSKliaMQfZKVtKVG85D1URnBJyWVo42ySoZ+iCHbmoMHq8Fa7C+TXbl9R nue8xy3GvpJhuTaPTJhupsUMhj9X+t6hCXaecz3NsL65Qt7/o4kcvOzKyIyRp03dxRgj 1GBofqiZcZL+WEMNzDrHtMRzDICTyHRFCFYbPXQlIgFfVwP1/6bgzgKhMs3khJl2VzVa iV+L7WTSS2PNI+fNejqfCiVnxEp0mot+Fc+91L9GtamcCg3bB0Cr81q7zpvtOzD6yQCg SPWMn+Kl6Z0iQ3s2g7Gg4DC1vu92zeH9ufutI6QLOSiMOYyOfX60irWq1SfzR0SwuR3l GxZg== X-Gm-Message-State: AOAM531/sn3kAlYmwZHZK9v46hHKWyfbQp1dX94MbHQGI97Sz7dyUNeL azj349jFFR+ZDGM3CFClrJe6ep7gcVe2O1fxRChw86Lt7zlw7a9acQbG/hOZBEsUowR/PBjs0al IkyhQShPtIcESO4ziEUnOcLfU2Za0D02Yo3OQ+ikaiOme8mGi0R5um5YW0fNNmqHhRnQH3g== X-Received: by 2002:ac8:7d89:: with SMTP id c9mr23379961qtd.74.1638564002069; Fri, 03 Dec 2021 12:40:02 -0800 (PST) X-Google-Smtp-Source: ABdhPJx+09mIjsMIuNsb38wc1m93zk27Y0xFPec02d6JANdveh0yw/HB0yt/R4g3sW3IW07jPn5bLg== X-Received: by 2002:ac8:7d89:: with SMTP id c9mr23379934qtd.74.1638564001625; Fri, 03 Dec 2021 12:40:01 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::6d7? ([2607:fea8:a262:5f00::6d7]) by smtp.gmail.com with ESMTPSA id a38sm2561744qkp.80.2021.12.03.12.40.00 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 03 Dec 2021 12:40:01 -0800 (PST) Message-ID: <69507e99-2f0a-1187-2701-ccfb240c77b3@redhat.com> Date: Fri, 3 Dec 2021 15:39:59 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.2 To: gcc-patches Subject: [PATCH 2/2] Use dominators to reduce ranger cache-flling. 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, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" When a request is made for the range of an ssa_name at some location, the first thing we do is invoke range_of_stmt() to ensure we have looked at the definition and have an evaluation for the name at a global level.  I recently added a patch which dramatically reduces the call stack requirements for that call. Once we have confirmed the definition range has been set, a call is made for the range-on-entry to the block of the use.  This is performed by the cache, which proceeds to walk the CFG predecessors looking for when ranges are created  (exported), existing range-on-entry cache hits,  or the definition block. Once this list of  predecessors has been created, a forward walk is done, pushing the range's through successor edges of all the blocks  were visited in the initial walk. If the use is far from the definition, we end up filling a lot of the same value on these paths.  Also uses which are far from a range-modifying statement push the same value into a lot of blocks. This patch tries to address at least some inefficiencies.  It recognizes that First, if there is no range modifying stmt between this use and the last range we saw in a dominating block, we can just use the value from the dominating block and not fill in all the cache entries between here and there.  This is the biggest win. Second. if there is a range modifying statement at the end of some block, we will have to do the appropriate cache walk to this point, but its possible the range-on-entry to THAT block might be able to use a dominating range, and we can prevent the walk from going any further than this block Combined, this should prevent a lot of unnecessary ranges from being plugging into the cache. ie, to visualize: bb4:   a = foo() <..> bb60:    if (a < 30) <...> bb110:     g = a + 10 if the first place we ask for a is in bb110, we walk the CFG from 110 all the way back to bb4, on all paths leading back. then fill all those cache entries. With this patch,   a) if bb60 does not dominate bb110, the request will scan the dominators, arrive at the definition block, have seen no range modifier, and simply set the on-entry for 110 to the range of a. done.   b) if bb60 does dominate 110, we have no idea which edge out of 60 dominates it, so we will revert to he existing cache algorithm.  Before doing so, it checks and determines that there are no modifiers between bb60 and the def in bb4, and so sets the on-entry cache for bb60 to be the range of a.   Now when we do the cache fill walk, it only has to go back as far as bb60 instead of all the way to bb4. Otherwise we just revert to what we do now (or if dominators are not available).   I have yet to see a case where we miss something we use to get, but that does not mean there isn't one :-). The cumulative performance impact of this compiling a set of 390 GCC source files at -O2 (measured via callgrind) is pretty decent:  Negative numbers are a compile time decrease.  Thus -10% is 10% faster compilation time. EVRP     : %change from trunk is -26.31% (!) VRP2     : %change from trunk is -9.53% thread_jumps_full   : %change from trunk is -15.8% Total compilation time  : %change from trunk is -1.06% So its not insignificant. Risk would be very low, unless dominators are screwed up mid-pass.. but then the relation code would be screwed up too. Bootstrapped on  x86_64-pc-linux-gnu with no regressions. OK? Andrew From ea2f90151dcaeea2b5c372f900e1eef735269e18 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 3 Dec 2021 11:02:19 -0500 Subject: [PATCH 2/2] Use dominators to reduce cache-flling. Before walking the CFG and filling all cache entries, check if the same information is available in a dominator. * gimple-range-cache.cc (ranger_cache::fill_block_cache): Check for a range from dominators before filling the cache. (ranger_cache::range_from_dom): New. --- gcc/gimple-range-cache.cc | 73 +++++++++++++++++++++++++++++++++++++++ gcc/gimple-range-cache.h | 1 + 2 files changed, 74 insertions(+) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index fe31e9462aa..47e95ec23be 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1312,6 +1312,20 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) fprintf (dump_file, " : "); } + // If there are dominators, check if a dominators can supply the range. + if (dom_info_available_p (CDI_DOMINATORS) + && range_from_dom (block_result, name, bb)) + { + m_on_entry.set_bb_range (name, bb, block_result); + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "Filled from dominator! : "); + block_result.dump (dump_file); + fprintf (dump_file, "\n"); + } + return; + } + while (m_workback.length () > 0) { basic_block node = m_workback.pop (); @@ -1394,3 +1408,62 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) fprintf (dump_file, " Propagation update done.\n"); } + +// Check to see if we can simply get the range from the dominator. + +bool +ranger_cache::range_from_dom (irange &r, tree name, basic_block bb) +{ + gcc_checking_assert (dom_info_available_p (CDI_DOMINATORS)); + + // Search back to the definition block or entry block. + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + if (def_bb == NULL) + def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); + + // Flag if we encounter a block with non-null set. + bool non_null = false; + for (bb = get_immediate_dominator (CDI_DOMINATORS, bb); + bb && bb != def_bb; + bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + { + // If there is an outgoing range, the on-entry value won't work. + if (m_gori.has_edge_range_p (name, bb)) + { + // Check if we can seed this block with a dominator value. THis will + // prevent the ache from being filled back further than this. + if (bb != def_bb && range_from_dom (r, name, bb)) + m_on_entry.set_bb_range (name, bb, r); + return false; + } + + // Flag if we see a non-null reference during this walk. + if (m_non_null.non_null_deref_p (name, bb, false)) + non_null = true; + + // If range-on-entry is set in this block, it can be used. + if (m_on_entry.get_bb_range (r, name, bb)) + { + // Apply non-null if appropriate. + if (r.varying_p () && non_null) + { + gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); + r.set_nonzero (TREE_TYPE (name)); + } + return true; + } + } + // If this is the def block, and NAME is an export, then this value + // cannot be used. + if (bb == def_bb && m_gori.has_edge_range_p (name, bb)) + return false; + + // Otherwise choose the global value and use it. + get_global_range (r, name); + if (r.varying_p () && non_null) + { + gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); + r.set_nonzero (TREE_TYPE (name)); + } + return true; +} diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index eb7a875c46b..2c52a0b6ce3 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -98,6 +98,7 @@ public: virtual bool range_of_expr (irange &r, tree name, gimple *stmt); virtual bool range_on_edge (irange &r, edge e, tree expr); bool block_range (irange &r, basic_block bb, tree name, bool calc = true); + bool range_from_dom (irange &r, tree name, basic_block bb); bool get_global_range (irange &r, tree name) const; bool get_global_range (irange &r, tree name, bool ¤t_p); -- 2.17.2