From patchwork Tue Dec 7 20:19:05 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1564849 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=VyOF9C3K; 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 4J7s8h0G79z9s0r for ; Wed, 8 Dec 2021 07:19:32 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D14C43857C44 for ; Tue, 7 Dec 2021 20:19:29 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D14C43857C44 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1638908369; bh=4omSTWt1DsUBgj2PQBjNYGzC91npWnrqjK43Y8xMAhc=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=VyOF9C3KvIcDoGUx9TJdcZj2OOfEUP9IDsmOXZxJkYb1iI5Jqtwjfg6i6E50Y5gKV LEJhQ66IEkgXWCep+uqcW5NHsMbBd1mC0oUXytu8VBXjfYEig+CWv5MxXtjwbRt6Eo 3t1Zma4Sz/+RjxzEdI6eVI+iOXYjslecB6WF43+A= 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 DE5353858D28 for ; Tue, 7 Dec 2021 20:19:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DE5353858D28 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-186-96jW_ZYNMYOi63U0STVz7w-1; Tue, 07 Dec 2021 15:19:08 -0500 X-MC-Unique: 96jW_ZYNMYOi63U0STVz7w-1 Received: by mail-qv1-f72.google.com with SMTP id dz17-20020ad45891000000b003bbb4aba6d7so874199qvb.12 for ; Tue, 07 Dec 2021 12:19:08 -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; bh=8qiPptryxK6sIwV+5d7c+PEuR2oEJgRo4BhKUSFSdo0=; b=oxCnate1cP12yOdxfblr3tem9tXNJexDkiibnu/mlz9l6V+7KBIwo2+jY4lRZrtdbm rjM1Ub6wohI7b96TJ1rQIyxg9lAJ2KArzBu83lfSOoE+PaNlqUtt2WfVKR88iepuEZoo /cYK9RJyb+sHCEaiUVt0QQoWNA1AGDiL7tdChCNk00eA+3QlF9zIRMJptcJbJ1h1DyYB Jm/y13KHYjzsB/gBi7lIx9KN8YNgMA2Y4BRe/+1wvIKuFbgrVc3RDyLXPV8Dyvoe9b3x rH5iXTUD1fKD7c88WVqv4ECFLRWIc39wyVNXIpXur3h2Wwi5ToqYAcz06d1SJbKM7y6Q Z/kg== X-Gm-Message-State: AOAM531LkbS+YOWfEB7hi33S9wZtOIKuO4eptJhwiS/8k+kDvQ8cmRI5 fLJL8K1JTg7vhNgURwftsDeusDDd7r/w3shTFGC3p3zlh1lPSJsloVqb31KEcxtp8w0xqNW7kYh kVSzVBDnFvu8gAjjWckUabbEq3beyLEM+sQ88XgrHGlgLYNT0JYGfn4Jw5JD1TXEpfH5srg== X-Received: by 2002:a37:a64f:: with SMTP id p76mr1844474qke.154.1638908347561; Tue, 07 Dec 2021 12:19:07 -0800 (PST) X-Google-Smtp-Source: ABdhPJyErdGOVjjoaOZ3BnICw3lUue9N2uHV5XIoEM0VIdqIW/bP1L2rgBxpFDM7KJICUh9qSZYSvA== X-Received: by 2002:a37:a64f:: with SMTP id p76mr1844439qke.154.1638908347264; Tue, 07 Dec 2021 12:19:07 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00::a0bd? ([2607:fea8:a262:5f00::a0bd]) by smtp.gmail.com with ESMTPSA id s4sm372994qko.47.2021.12.07.12.19.06 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 07 Dec 2021 12:19:06 -0800 (PST) Message-ID: Date: Tue, 7 Dec 2021 15:19:05 -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][GCC11] PR tree-optimization/103603 - Directly resolve range_of_stmt dependencies. (Port of PR 103231/103464) X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.2 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+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" The following patch is a slight rework of the 2 patches which flatten rangers call stack.  It needed some tweaking since some of the routines have changed name or been adjusted. This has been bootstrapped on x86_64-pc-linux-gnu with no regressions.  OK for gcc-11 release branch? Andrew commit 027ee39a809addd9ecd577ea894de6c8987c0914 Author: Andrew MacLeod Date: Tue Dec 7 12:09:33 2021 -0500 Directly resolve range_of_stmt dependencies. (Port of PR 103231/103464) 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/103603 gcc/ * gimple-range.cc (gimple_ranger::gimple_ranger): Create stmt stack. (gimple_ranger::~gimple_ranger): New. (gimple_ranger::range_of_stmt): Process dependencies 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. diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index f71ee6663fd..f861459ed96 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -358,6 +358,22 @@ gimple_range_calc_op2 (irange &r, const gimple *stmt, op1_range); } +// Construct a gimple_ranger. + +gimple_ranger::gimple_ranger () : m_cache (*this) +{ + m_stmt_list.create (0); + m_stmt_list.safe_grow (num_ssa_names); + m_stmt_list.truncate (0); +} + +// Destruct a gimple_ranger. + +gimple_ranger::~gimple_ranger () +{ + m_stmt_list.release (); +} + // Calculate a range for statement S and return it in R. If NAME is provided it // represents the SSA_NAME on the LHS of the statement. It is only required // if there is more than one lhs/output. If a range cannot @@ -1069,6 +1085,9 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) if (m_cache.get_non_stale_global_range (r, name)) return true; + // Avoid deep recursive call chains. + prefill_stmt_dependencies (name); + // Otherwise calculate a new value. int_range_max tmp; calc_stmt (tmp, s, name); @@ -1087,6 +1106,111 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) return true; } +// 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); + // Only pre-process range-ops and PHIs. + if (!gimple_range_handler (stmt) && !is_a (stmt)) + return; + + // If this op has not been processed yet, then push it on the stack + if (!m_cache.get_global_range (r, name)) + { + // Set as current. + m_cache.get_non_stale_global_range (r, name); + 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; + gimple *stmt = SSA_NAME_DEF_STMT (ssa); + gcc_checking_assert (stmt && gimple_bb (stmt)); + + // Only pre-process range-ops and PHIs. + if (!gimple_range_handler (stmt) && !is_a (stmt)) + return; + + // Mark where on the stack we are starting. + unsigned start = m_stmt_list.length (); + m_stmt_list.safe_push (ssa); + + if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) + { + fprintf (dump_file, "Range_of_stmt dependence fill starting at"); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + + // 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); + calc_stmt (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 (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) + { + fprintf(dump_file, " 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); + } + + gphi *phi = dyn_cast (stmt); + if (phi) + { + for (unsigned x = 0; x < gimple_phi_num_args (phi); x++) + prefill_name (r, gimple_phi_arg_def (phi, x)); + } + else + { + 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 (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) + fprintf (dump_file, "END range_of_stmt dependence fill\n"); +} + // This routine will export whatever global ranges are known to GCC // SSA_RANGE_NAME_INFO fields. diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 5751b0937a0..caa12e4c4d5 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -46,7 +46,8 @@ along with GCC; see the file COPYING3. If not see class gimple_ranger : public range_query { public: - gimple_ranger () : m_cache (*this) { } + 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; @@ -55,11 +56,14 @@ public: void export_global_ranges (); void dump (FILE *f); protected: + void prefill_name (irange &r, tree name); + void prefill_stmt_dependencies (tree ssa); bool calc_stmt (irange &r, gimple *s, tree name = NULL_TREE); bool range_of_range_op (irange &r, gimple *s); bool range_of_call (irange &r, gcall *call); bool range_of_cond_expr (irange &r, gassign* cond); ranger_cache m_cache; + vec m_stmt_list; private: bool range_of_phi (irange &r, gphi *phi); bool range_of_address (irange &r, gimple *s);