From patchwork Thu Mar 17 17:35:10 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1606693 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=TqPuSoUD; 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 4KKDnv14nMz9s8s for ; Fri, 18 Mar 2022 04:36:02 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 79641385DC3B for ; Thu, 17 Mar 2022 17:35:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 79641385DC3B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1647538559; bh=lyymgl5Us77bs5XtBfV1Px89m0eRWkY8XXApoe7DIoE=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=TqPuSoUD+9mqVn2E7QvHizU6tZibqPrPCLaGERm7i2y3oN7hy1joQg1EtAwpqPik/ TOxVIjEGpm+QZQvkHgF2APOpGzPAy0yidmM/3Tr8gIgrX8LbAtQ6AvU5jrAU31Oh92 nx+yrJp402B47YtLgKcv2vn4Qo5N8veW6Ukf6c5k= 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 1B76E3858D1E for ; Thu, 17 Mar 2022 17:35:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 1B76E3858D1E Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-626-BJd3qVEMM06nVgOzN_Y_2A-1; Thu, 17 Mar 2022 13:35:14 -0400 X-MC-Unique: BJd3qVEMM06nVgOzN_Y_2A-1 Received: by mail-qk1-f197.google.com with SMTP id u17-20020a05620a431100b004765c0dc33cso3812043qko.14 for ; Thu, 17 Mar 2022 10:35:14 -0700 (PDT) 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:cc:from:subject; bh=WcsUq74+qLPkFukNaeVewjdt36UJWjFdh1uzIGflpM0=; b=I08AJDev5omg1ejQUL+NKP/6w68RrrWDqnNC1a5OE6RmpbHPtEervTf6w9f7v9y+LC OOXGUtMvE+VePNERzrNInmc+UtbyGg8oVILpezcqDzVVBX6Vz8JHmicOtk6299+26Cnq iUO9MyOtVP2WCrp6KGQyOff4EI7JRWnbPNEVhJGmpeKho/NluB3dTRyHx6DaJtcr1VqK D54RggD3XJZz0j7FkBvLvYDjGFzNrvJhScWhicE+8p64/1Enr/ZZB54jyP/PWyIlUdrF hSrNeIKNZiDQuKnhlxeonzF1hmfYXFYTScO445GpwB+sb+HKZ+IosDnKHgvILgtMa255 mBGg== X-Gm-Message-State: AOAM531vfuM6jraxOT6hd8VZ//pXIaK1CEUSRzQvFH14F9Hs3DDlZzDI sDwcrQ2o38LNdO9x4kVGqVa7R+Kweev72uicH5sNGA0T/SnCb4pQ4Tt3Io2BXgTF5JGHcc8sSuG cbe2tSXZwqbLDzNShlHXlbms8JeimIsUbWFVcApgIQPGB4TMtzy7aSRBbVfjdU5qoy77TCw== X-Received: by 2002:ad4:5aea:0:b0:440:a2ec:eaa5 with SMTP id c10-20020ad45aea000000b00440a2eceaa5mr4171412qvh.106.1647538513803; Thu, 17 Mar 2022 10:35:13 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxNpR2ojrHS0t06biXrdV7R3DMP+3eVrGDC2zZDKqHrD3W99UvsUsYFAM1wceEyjMwNe4xoSw== X-Received: by 2002:ad4:5aea:0:b0:440:a2ec:eaa5 with SMTP id c10-20020ad45aea000000b00440a2eceaa5mr4171394qvh.106.1647538513528; Thu, 17 Mar 2022 10:35:13 -0700 (PDT) Received: from ?IPV6:2607:fea8:a262:5f00::9b6f? ([2607:fea8:a262:5f00::9b6f]) by smtp.gmail.com with ESMTPSA id o27-20020a05620a111b00b0067d5f359007sm2672485qkk.23.2022.03.17.10.35.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 17 Mar 2022 10:35:12 -0700 (PDT) Message-ID: Date: Thu, 17 Mar 2022 13:35:10 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.7.0 To: gcc-patches Subject: [PATCH] PR tree-optimization/102943 - Always use dominators in the cache when available. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.3 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_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, 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" As discussed in the PR, this patch adjusts rangers cache query to *always* use dominators to lookup ranges in the cache. It use to give up if it encountered a block with outgoing edge ranges. This patch changes that to continue looking back until a value is found, then applies any outgoing ranges encountered along the way. This prevents us from filling the on-entry cache in blocks which don't really affect the outcome, and causes significant memory reduction is large functions at a nominal calculation cost. I have tweaked the debug output as well as a couple of other little things from the original patch attached in the PR. Confirmed that the performance results are similar, and generated reams of debug output to ensure there are no issues there. Bootstraps on x86_64-pc-linux-gnu with no regressions.  OK for trunk? Andrew commit bcb3f3534412e1774ac9791f0de7ceb000bf2184 Author: Andrew MacLeod Date: Thu Mar 17 10:52:10 2022 -0400 Always use dominators in the cache when available. This patch adjusts range_from_dom to follow the dominator tree through the cache until value is found, then apply any outgoing ranges encountered along the way. This reduces the amount of cache storage required. PR tree-optimization/102943 * gimple-range-cache.cc (ranger_cache::range_from_dom): Find range via dominators and apply intermediary outgoing edge ranges. diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 583ba29eb63..421ea1a20ef 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -33,6 +33,7 @@ along with GCC; see the file COPYING3. If not see #include "attribs.h" #include "gimple-iterator.h" #include "gimple-walk.h" +#include "cfganal.h" #define DEBUG_RANGE_CACHE (dump_file \ && (param_ranger_debug & RANGER_DEBUG_CACHE)) @@ -1398,62 +1399,108 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) } -// Check to see if we can simply get the range from the dominator. +// Get the range of NAME from dominators of BB and return it in R. bool -ranger_cache::range_from_dom (irange &r, tree name, basic_block bb) +ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb) { - gcc_checking_assert (dom_info_available_p (CDI_DOMINATORS)); + if (!dom_info_available_p (CDI_DOMINATORS)) + return false; // 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); + basic_block bb; + basic_block prev_bb = start_bb; // 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)) + + // Range on entry to the DEF block should not be queried. + gcc_checking_assert (start_bb != def_bb); + m_workback.truncate (0); + + // Default value is global range. + get_global_range (r, name); + + // Search until a value is found, pushing outgoing edges encountered. + for (bb = get_immediate_dominator (CDI_DOMINATORS, start_bb); + bb; + prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb)) { - // If there is an outgoing range, the on-entry value won't work. + if (!non_null) + non_null |= m_non_null.non_null_deref_p (name, bb, false); + + // This block has an outgoing range. 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; + // Only outgoing ranges to single_pred blocks are dominated by + // outgoing edge ranges, so only those need to be considered. + edge e = find_edge (bb, prev_bb); + if (e && single_pred_p (prev_bb)) + m_workback.quick_push (prev_bb); } - // 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 (def_bb == bb) + break; - // If range-on-entry is set in this block, it can be used. if (m_on_entry.get_bb_range (r, name, bb)) + break; + } + + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "CACHE: BB %d DOM query, found ", start_bb->index); + r.dump (dump_file); + if (bb) + fprintf (dump_file, " at BB%d\n", bb->index); + else + fprintf (dump_file, " at function top\n"); + } + + // Now process any outgoing edges that we seen along the way. + while (m_workback.length () > 0) + { + int_range_max edge_range; + prev_bb = m_workback.pop (); + edge e = single_pred_edge (prev_bb); + bb = e->src; + + if (m_gori.outgoing_edge_range_p (edge_range, e, name, *this)) { - // Apply non-null if appropriate. - if (r.varying_p () && non_null) + r.intersect (edge_range); + if (r.varying_p () && ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)) { - gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); - r.set_nonzero (TREE_TYPE (name)); + if (m_non_null.non_null_deref_p (name, bb, false)) + { + gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); + r.set_nonzero (TREE_TYPE (name)); + } + } + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "CACHE: Adjusted edge range for %d->%d : ", + bb->index, prev_bb->index); + r.dump (dump_file); + fprintf (dump_file, "\n"); } - 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) + // Apply non-null if appropriate. + if (non_null && r.varying_p () + && !has_abnormal_call_or_eh_pred_edge_p (start_bb)) { gcc_checking_assert (POINTER_TYPE_P (TREE_TYPE (name))); r.set_nonzero (TREE_TYPE (name)); } + if (DEBUG_RANGE_CACHE) + { + fprintf (dump_file, "CACHE: Range for DOM returns : "); + r.dump (dump_file); + fprintf (dump_file, "\n"); + } return true; }