From patchwork Tue Nov 23 17:02:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 48030 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 18EE53858D28 for ; Tue, 23 Nov 2021 17:03:08 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 18EE53858D28 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1637686988; bh=59L4+9CDVYg7dANInIL3JrlJIyRMNli+IgUlIWFXIdg=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=u1K35WhyY53YcU6B4v58QAxhO8hDZSC7jPnOmSE4zWbtzqQMKmzMfDBstGhSXiBZy msv9tDCAgkiOtdSUkvvsY0fVXZaDbc3gcnvX8R1/yA89B/SPWOm/7sgmXYrq18wz/V kXXcd4QbHNGaPJhQ04sNe6uJk1N7WowoYD1tsj68= 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 195A43858D28 for ; Tue, 23 Nov 2021 17:02:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 195A43858D28 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-468-j6_WWuOaMQ6fBJP9d_g6rA-1; Tue, 23 Nov 2021 12:02:26 -0500 X-MC-Unique: j6_WWuOaMQ6fBJP9d_g6rA-1 Received: by mail-qv1-f69.google.com with SMTP id kj12-20020a056214528c00b003bde2e1df71so19585564qvb.18 for ; Tue, 23 Nov 2021 09:02:26 -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=c6ct8faqMcFM2hcYUOrTibJLg3/2I8LUtcEsfoipSAs=; b=hUGDagAf2lGIccibKEN+xeOZYUegqeGTnt7xQbEbtLv4hjWkWgrkPCi3BMoNFjFXmT FQv8y/Ng3EGqiwT1nXGs5DZNC8toWZf29tlOlDNXknzU91NyymgFwzJgWiTvl2bBm44B tk1mJoehs154wYJSaFpTiRRk2NA5CBty4ZGVsRj5yktfNSQPUqgSR9y6h9Q1K917EETE XATcLUdaqhDgsIrykrZ21S066y0k3J2ZamgDkt0fI4YuDceaWjWSeYJZQ+SSv78MBZV/ 54312IhFxMD/8Whca/wWSAUxWyFONpaVWzCk51WB5UduUnEaF5I4ahKTvs3eLbneLU+8 VNQQ== X-Gm-Message-State: AOAM530l5nXLZKxHZNHsrR0PE+KNOFmVyowZ6TonJVRoukyBQEOWqVL1 eGeovLgVQ7AXyTzl9WaRv/cDSRkmo+5HyF1n3AviAQODTUMjx6DxD6VI6UdYlrsW3XkjHe3tG9s gcPUsabIKeUuJOLir2DaSPov1Dc0pwsenEpm5ktHxoXzfs3XTpMCkS9ZSC01gUAGa8tydQA== X-Received: by 2002:a05:6214:240c:: with SMTP id fv12mr8195399qvb.58.1637686945032; Tue, 23 Nov 2021 09:02:25 -0800 (PST) X-Google-Smtp-Source: ABdhPJwPy2xvUcnd25mN8ecespXX2JXjlaITYcWowerTfEKKFYtzh4u3aZXKMpDXuWeJxQl+E1asLg== X-Received: by 2002:a05:6214:240c:: with SMTP id fv12mr8195358qvb.58.1637686944736; Tue, 23 Nov 2021 09:02:24 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::38cf? ([2607:fea8:a262:5f00::38cf]) by smtp.gmail.com with ESMTPSA id bq43sm6889493qkb.32.2021.11.23.09.02.23 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 23 Nov 2021 09:02:23 -0800 (PST) Message-ID: Date: Tue, 23 Nov 2021 12:02:22 -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 1/2] Split return functionality of get_non_stale_global_range. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.6 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_H2, 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" This is the first of 2 patches which will reduce the depth of the call chain in ranger. This patch simply splits the functionality of the routine get_non_stale_global_range() from a single boolean return to a boolean return and a bool reference. This routine queries the global cache for a value.  If  there is no value, it queries the legacy global range and sets it to that value.  If there was a value, it checks the temporal cache to see if its current, and if it is, returns TRUe plus the range. If the value is not currrent, or it was set to the legacy global value, then the timestamp is marked as "always current" as it indicates a calculation is ongoing, and we dont want to trigger any additional temporal faults until the calculation is done. And finallt FALSE is returned for all these cases. The second patch in the series wants to disambiguate at the call site whether this was a failure due to not being in the global cache, or whether it was due to the timestamp being out of date and take different actions for each case.   Details in the following note. This has been Bootstrapped on x86_64-pc-linux-gnu with no regressions.  OK? Andrew From 310719594aa20e8d012f478ab3208f889b558bac Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 19 Nov 2021 12:59:12 -0500 Subject: [PATCH 2/3] Split return functionality of get_non_stale_global_range. Get_non_stale_global_range returns true only when there is a cache entry that is not out of date. Change it so that it returns true if there was a cache value, but return the temporal comparison result in an auxiallary flag. * gimple-range-cache.cc (ranger_cache::get_global_range): Always return a range, return if it came from the cache or not. (get_non_stale_global_range): Rename to get_global_range, and return the temporal state in a flag. * gimple-range-cache.h (get_non_stale_global_range): Rename and adjust. * gimple-range.cc (gimple_ranger::range_of_expr): No need to query get_global_range. (gimple_ranger::range_of_stmt): Adjust for global cache temporal state returned in a flag. --- gcc/gimple-range-cache.cc | 55 ++++++++++++++++++++------------------- gcc/gimple-range-cache.h | 2 +- gcc/gimple-range.cc | 21 ++++++++------- 3 files changed, 41 insertions(+), 37 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index b347edeb474..fe31e9462aa 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -923,44 +923,45 @@ ranger_cache::dump_bb (FILE *f, basic_block bb) } // Get the global range for NAME, and return in R. Return false if the -// global range is not set. +// global range is not set, and return the legacy global value in R. bool ranger_cache::get_global_range (irange &r, tree name) const { - return m_globals.get_global_range (r, name); + if (m_globals.get_global_range (r, name)) + return true; + r = gimple_range_global (name); + return false; } -// Get the global range for NAME, and return in R if the value is not stale. -// If the range is set, but is stale, mark it current and return false. -// If it is not set pick up the legacy global value, mark it current, and -// return false. -// Note there is always a value returned in R. The return value indicates -// whether that value is an up-to-date calculated value or not.. +// Get the global range for NAME, and return in R. Return false if the +// global range is not set, and R will contain the legacy global value. +// CURRENT_P is set to true if the value was in cache and not stale. +// Otherwise, set CURRENT_P to false and mark as it always current. +// If the global cache did not have a value, initialize it as well. +// After this call, the global cache will have a value. bool -ranger_cache::get_non_stale_global_range (irange &r, tree name) +ranger_cache::get_global_range (irange &r, tree name, bool ¤t_p) { - if (m_globals.get_global_range (r, name)) - { - // Use this value if the range is constant or current. - if (r.singleton_p () - || m_temporal->current_p (name, m_gori.depend1 (name), - m_gori.depend2 (name))) - return true; - } + bool had_global = get_global_range (r, name); + + // If there was a global value, set current flag, otherwise set a value. + current_p = false; + if (had_global) + current_p = r.singleton_p () + || m_temporal->current_p (name, m_gori.depend1 (name), + m_gori.depend2 (name)); else - { - // Global has never been accessed, so pickup the legacy global value. - r = gimple_range_global (name); - m_globals.set_global_range (name, r); - } - // After a stale check failure, mark the value as always current until a - // new one is set. - m_temporal->set_always_current (name); - return false; + m_globals.set_global_range (name, r); + + // If the existing value was not current, mark it as always current. + if (!current_p) + m_temporal->set_always_current (name); + return current_p; } -// Set the global range of NAME to R. + +// Set the global range of NAME to R and give it a timestamp. void ranger_cache::set_global_range (tree name, const irange &r) diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 49c13d1e85f..eb7a875c46b 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -100,7 +100,7 @@ public: bool block_range (irange &r, basic_block bb, tree name, bool calc = true); bool get_global_range (irange &r, tree name) const; - bool get_non_stale_global_range (irange &r, tree name); + bool get_global_range (irange &r, tree name, bool ¤t_p); void set_global_range (tree name, const irange &r); void propagate_updated_value (tree name, basic_block bb); diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 9ca568ce55d..e3ab3a8bb48 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -85,8 +85,7 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) if (!stmt) { int_range_max tmp; - if (!m_cache.get_global_range (r, expr)) - r = gimple_range_global (expr); + m_cache.get_global_range (r, expr); // Pick up implied context information from the on-entry cache // if current_bb is set. Do not attempt any new calculations. if (current_bb && m_cache.block_range (tmp, current_bb, expr, false)) @@ -282,15 +281,19 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) } else if (!gimple_range_ssa_p (name)) res = get_tree_range (r, name, NULL); - // Check if the stmt has already been processed, and is not stale. - else if (m_cache.get_non_stale_global_range (r, name)) - { - if (idx) - tracer.trailer (idx, " cached", true, name, r); - return true; - } else { + bool current; + // Check if the stmt has already been processed, and is not stale. + if (m_cache.get_global_range (r, name, current)) + { + if (current) + { + if (idx) + tracer.trailer (idx, " cached", true, name, r); + return true; + } + } // Otherwise calculate a new value. int_range_max tmp; fold_range_internal (tmp, s, name); -- 2.17.2 From patchwork Tue Nov 23 17:02:33 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 48031 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 79566385841B for ; Tue, 23 Nov 2021 17:04:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 79566385841B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1637687051; bh=R9ihVFPgVlK+i+IALaL5M+Ts4n099w7PguIepXjkJPQ=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=WcLcFigOihqWAyGsgHpvlvZB58wsLjNHYCW/vIIsWJQBnKWqCfTi+keIx3pS3FxKp eO3LvH02QlJ3EGwzBukihajB/Myqp2qG1ts2fD+T58Ao1s1S6A5nFW7DUpZyVxAmw/ G1a5J/gCQXCDB+xTb70W6Z10ldAWDfiRIAwUD3X8= 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 D32D63858C2C for ; Tue, 23 Nov 2021 17:02:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D32D63858C2C 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-425-mk7rFxePPk2LAU_1PqYSPg-1; Tue, 23 Nov 2021 12:02:36 -0500 X-MC-Unique: mk7rFxePPk2LAU_1PqYSPg-1 Received: by mail-qt1-f198.google.com with SMTP id h13-20020ac87d4d000000b002af9c496444so13554610qtb.22 for ; Tue, 23 Nov 2021 09:02:36 -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:cc:from:subject; bh=VQV2sLC2r+P73rX0DMYScI4gCgsIKZywwZL457CXdPo=; b=i6pkz1DOJWyHRNEe3xMQCERQNeyCMDDVt7asxjDJJEIlPm5/6r05n28v+ihrTrEnEC 3ljzn/Y/eB7ZUgutJFKZYzC1b5bBKro5lhA61kWjGMPDrhLLe8fRYAam1Syd4wr8mCng xHGP4BPG2rGDo4vRP+PNx1YdrcCx3yDtklwCRkZVEudcwIglg3Q6jmGeJ0b4vmiL795q 7q4AY2j5aBqE37V2mOKMvWWCoJaRGD5WYRrT7GMJIXrwEjl9T5qMqkdDxf/hmylbEAhZ FwNNxTYRE5OwJ9eEvpO4x64GEd2kixT3A0G8LZlDPcVOh3IFFo/54xQp8chX54FT4T97 /VTA== X-Gm-Message-State: AOAM531iZmAw7x7VjXNLIGPlYNO+CBS7sDkEXoGzRoqgbUfQiOjEmM38 IgD7H0C/d0GKb1G9IfrLNjjjAg1uLnel4Jri2eNcH2hnf14EVY6R7FvMuHEHt3EVbApCX+L1/wD NLhY8qh41TJm9fy7rGGoC7Q0qZUcluSLYeIOn6tktb8XvF88QHSXgCk32dHPmITAxhJxXlw== X-Received: by 2002:a05:6214:12d:: with SMTP id w13mr8294497qvs.39.1637686955730; Tue, 23 Nov 2021 09:02:35 -0800 (PST) X-Google-Smtp-Source: ABdhPJzA5YKLidfdkCnmoITXUQWeMA/OBJOsM2TkSJ9ippO9wNuHRzwUE0beM3r2AFMG0+J8ipcYVQ== X-Received: by 2002:a05:6214:12d:: with SMTP id w13mr8294461qvs.39.1637686955470; Tue, 23 Nov 2021 09:02:35 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::38cf? ([2607:fea8:a262:5f00::38cf]) by smtp.gmail.com with ESMTPSA id bj30sm6752699qkb.58.2021.11.23.09.02.33 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 23 Nov 2021 09:02:34 -0800 (PST) Message-ID: <155ced1e-67fb-7cfb-f94a-138e2b2ead35@redhat.com> Date: Tue, 23 Nov 2021 12:02:33 -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] PR tree-optimization/103231 - Directly resolve range_of_stmt dependencies. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.6 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, 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-Content-Filtered-By: Mailman/MimeDel 2.1.29 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 is the second patch in the series. Ranger uses its own API to recursively satisfy dependencies. When range_of_stmt is called on _1482 = _1154 + _1177;  it picks up the ranges of _1154 and _1177 from it's cache. If those statements have not been seen yet, it recursively calls range_of_stmt on each one to resolve the answer.  Each main API call can trigger up to 5 other calls to get to the next API point: gimple_ranger::fold_range_internal (...) gimple_ranger::range_of_stmt (_1154,...) gimple_ranger::range_of_expr (_1154,....) fold_using_range::range_of_range_op (..) fold_using_range::fold_stmt (...) gimple_ranger::fold_range_internal (...) gimple_ranger::range_of_stmt (_1482,...) For a normal forward walk, values tend to already be in the cache, but when we try to answer a range_on_edge question on a back edge, it can trigger a very long series of queries.  I spent some time analyzing these patterns, and found that regardless of which API entry point was used, ultimately range_of_stmt is invoked in a predictable order to initiate the cache values. This patch implements a dependency resolver which when range_of_stmt uses when it is called on something which does not have a cache entry yet (thus the disambiguation of the temporal failure vs lack of cache entry in the previous patch) This looks at each operand, and if that operand does not have a cache entry, pushes it on a stack.   Names are popped from the stack and fold_using_range() is invoked once all the operands have been resolved.   When we do get to call fold_using_range::fold_stmt(), we are sure the operands are cached and the value will simply be calculated.  This is ultimately the exact series of events that would have happened had the main API been used... except we don't involve the call stack anymore for each one. Well, mostly :-).  For this fix, we only do this with operands of stmts which have a range-ops handler.. meaning we do not use the API for anything range-ops understands.  We will still use the main API for resolving PHIS and other statements as they are encountered.    We could do this for PHIS as well, but for the most part it was the chains of stmts within a block that were causing the vast majority of the issue.  If we later discover large chains of PHIs are causing issues as well, then I can easily add them to this as well.  I avoided them this time because there is extra overhead involved in traversing all the PHI arguments extra times.  Sticking with range-ops limits us to 2 operands to check, and the overhead is very minimal. I have tested this with PHIs as well and we could just include them upfront. The overhead is more than doubled, but the increased compile time of a VRP pass is still under 1%. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  OK? Andrew From 28d1fea6e6c0c0368dbc04e895aaa0a6b47c19da Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Mon, 22 Nov 2021 14:39:41 -0500 Subject: [PATCH 3/3] Directly resolve range_of_stmt dependencies. All ranger API entries eventually call range_of_stmt to ensure there is an initial global value to work with. This can cause very deep call chains when satisfied via the normal API. Instead, push any dependencies onto a stack and evaluate them in a depth first manner, mirroring what would have happened via the normal API calls. PR tree-optimization/103231 gcc/ * gimple-range.cc (gimple_ranger::gimple_ranger): Create stmt stack. (gimple_ranger::gimple_ranger): Delete stmt stack. (gimple_ranger::range_of_stmt): Process depenedencies if they have no global cache entry. (gimple_ranger::prefill_name): New. (gimple_ranger::prefill_stmt_dependencies): New. * gimple-range.h (class gimple_ranger): Add prototypes. --- gcc/gimple-range.cc | 107 +++++++++++++++++++++++++++++++++++++++++++- gcc/gimple-range.h | 4 ++ 2 files changed, 109 insertions(+), 2 deletions(-) diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index e3ab3a8bb48..178a470a419 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -46,6 +46,9 @@ gimple_ranger::gimple_ranger () : m_oracle = m_cache.oracle (); if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE)) tracer.enable_trace (); + m_stmt_list.create (0); + m_stmt_list.safe_grow (num_ssa_names); + m_stmt_list.truncate (0); // Ensure the not_executable flag is clear everywhere. if (flag_checking) @@ -61,6 +64,11 @@ gimple_ranger::gimple_ranger () : } } +gimple_ranger::~gimple_ranger () +{ + m_stmt_list.release (); +} + bool gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) { @@ -284,9 +292,10 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) else { bool current; - // Check if the stmt has already been processed, and is not stale. + // Check if the stmt has already been processed. if (m_cache.get_global_range (r, name, current)) { + // If it isn't stale, use this cached value. if (current) { if (idx) @@ -294,7 +303,10 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) return true; } } - // Otherwise calculate a new value. + else + prefill_stmt_dependencies (name); + + // Calculate a new value. int_range_max tmp; fold_range_internal (tmp, s, name); @@ -311,6 +323,97 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) return res; } + +// Check if NAME is a dependency that needs resolving, and push it on the +// stack if so. R is a scratch range. + +inline void +gimple_ranger::prefill_name (irange &r, tree name) +{ + if (!gimple_range_ssa_p (name)) + return; + gimple *stmt = SSA_NAME_DEF_STMT (name); + if (!gimple_range_handler (stmt)) + return; + + bool current; + // If this op has not been processed yet, then push it on the stack + if (!m_cache.get_global_range (r, name, current)) + m_stmt_list.safe_push (name); +} + +// This routine will seed the global cache with most of the depnedencies of +// NAME. This prevents excessive call depth through the normal API. + +void +gimple_ranger::prefill_stmt_dependencies (tree ssa) +{ + if (SSA_NAME_IS_DEFAULT_DEF (ssa)) + return; + + int_range_max r; + unsigned idx; + gimple *stmt = SSA_NAME_DEF_STMT (ssa); + gcc_checking_assert (stmt && gimple_bb (stmt)); + + // Only pre-process range-ops. + if (!gimple_range_handler (stmt)) + return; + + // Mark where on the stack we are starting. + unsigned start = m_stmt_list.length (); + m_stmt_list.safe_push (ssa); + + idx = tracer.header ("ROS dependence fill\n"); + + // Loop until back at the start point. + while (m_stmt_list.length () > start) + { + tree name = m_stmt_list.last (); + // NULL is a marker which indicates the next name in the stack has now + // been fully resolved, so we can fold it. + if (!name) + { + // Pop the NULL, then pop the name. + m_stmt_list.pop (); + name = m_stmt_list.pop (); + // Don't fold initial request, it will be calculated upon return. + if (m_stmt_list.length () > start) + { + // Fold and save the value for NAME. + stmt = SSA_NAME_DEF_STMT (name); + fold_range_internal (r, stmt, name); + m_cache.set_global_range (name, r); + } + continue; + } + + // Add marker indicating previous NAME in list should be folded + // when we get to this NULL. + m_stmt_list.safe_push (NULL_TREE); + stmt = SSA_NAME_DEF_STMT (name); + + if (idx) + { + tracer.print (idx, "ROS dep fill ("); + print_generic_expr (dump_file, name, TDF_SLIM); + fputs (") at stmt ", dump_file); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + + gcc_checking_assert (gimple_range_handler (stmt)); + tree op = gimple_range_operand2 (stmt); + if (op) + prefill_name (r, op); + op = gimple_range_operand1 (stmt); + if (op) + prefill_name (r, op); + } + if (idx) + tracer.trailer (idx, "ROS ", false, ssa, r); +} + + // This routine will invoke the gimple fold_stmt routine, providing context to // range_of_expr calls via an private interal API. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 615496ec9b8..c2923c58b27 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -47,6 +47,7 @@ class gimple_ranger : public range_query { public: gimple_ranger (); + ~gimple_ranger (); virtual bool range_of_stmt (irange &r, gimple *, tree name = NULL) OVERRIDE; virtual bool range_of_expr (irange &r, tree name, gimple * = NULL) OVERRIDE; virtual bool range_on_edge (irange &r, edge e, tree name) OVERRIDE; @@ -61,9 +62,12 @@ public: bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree)); protected: bool fold_range_internal (irange &r, gimple *s, tree name); + void prefill_name (irange &r, tree name); + void prefill_stmt_dependencies (tree ssa); ranger_cache m_cache; range_tracer tracer; basic_block current_bb; + vec m_stmt_list; }; /* Create a new ranger instance and associate it with a function. -- 2.17.2