From patchwork Thu Oct 5 19:04:45 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 148990 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:612c:2016:b0:403:3b70:6f57 with SMTP id fe22csp508041vqb; Thu, 5 Oct 2023 12:06:03 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFuBpeAcCowuC0zSpAqbC0hxwKBpct+y415rlJ26P3KahBM8mt9/G3cHiPdyEouOJUJ7DSG X-Received: by 2002:a17:906:8e:b0:9a9:d5f4:1a0d with SMTP id 14-20020a170906008e00b009a9d5f41a0dmr4450070ejc.45.1696532763069; Thu, 05 Oct 2023 12:06:03 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1696532763; cv=none; d=google.com; s=arc-20160816; b=Y/e1UKuNh3XwGQOUXcKMCwWHS7T02a3X7WZdcKlxwzh3F2Cu1gpnwcMPsqx5iu+CBo y9tK8Z8p1HhIUSso1c+u5Y2NWNRNawbKlXl1yUJcHl/Dit7bEEdvKoTKWcsMmHiyp8Oe rLPBv20nTbkCITE6mU8Vx9/6ksLvVeIaIZraMRRwVpNHqYFvau46fesDwJf57V8bc3L0 ZnXhK/T4k1PDQ6kghnb/XR8a6JLk+ouPKeqatFf4Zv+tCUpvX5NW6voI+mQPJpQplS54 a5Df+3ehr8U3kVmPtXIwqSoVGuMV9QSBs6CuudMGEVHewzZwIFfqAD/u64fWnzwpoCTl LhRw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-language:subject:from :cc:to:user-agent:mime-version:date:message-id:dkim-signature :dmarc-filter:delivered-to; bh=tV9KqCbjLgU/sk0rUFcqEKLAb5iWk7fmUp2uJOZSzg0=; fh=ZE6EPE2PZ3ED3Eq5R4AB8kSxxMSuW2qQfXnHfqWWl4c=; b=SF25IU4VYT1F6bIbPsxBuk87OoIyfz/SiTJyggbZueNZK3gz5GaZlPY3/6Vj/Rl/7D kxygl7TBKzEp2TxOTapXvOrdMhsGkp6XCMk4M+P5te2W9bBw/4/UQ4sw9hVGF6ebHObd 2Gy3ybBGi7yY0QLXKyRxMoyS9d8FbhZSOd5wgUri0HtuBjFSHhwNJoBS26GdJiACoIP8 313yyigiJ1yy4GfXdtx6NcOi3aTfNHHJZ65yi3jGi1SxEspAhex5MGoEVn8+3ffTm1ma Lku49ckp3yYhO261ehXiFnwoeLnHAy9S1IO648lNqmqicq/hI7gMDXdIcwtafa1iTvCx wjlA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=QgAAbScX; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id v26-20020a1709064e9a00b0099279b2cdddsi899975eju.833.2023.10.05.12.06.02 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 05 Oct 2023 12:06:03 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=QgAAbScX; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C535A3861886 for ; Thu, 5 Oct 2023 19:05:15 +0000 (GMT) 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 C099A3858C5F for ; Thu, 5 Oct 2023 19:04:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C099A3858C5F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1696532687; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type; bh=tV9KqCbjLgU/sk0rUFcqEKLAb5iWk7fmUp2uJOZSzg0=; b=QgAAbScXMvGk0NFO/Fu2Sex1MK/Gm9GRl1O/b7UxIVOvs8EejtDlgt7CiYvnVBZ+aNBzQN bpeSzMw3nHNQTbURuGWkm+trr6ftIleId7ClIwAQcNhLjUkVZApe/aAQecXvx9qnil4pEg AHq6sRsqEuA+X3/yfa4tzkpT7snbOkk= 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.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-618-C8cVV3qQOjCNR6RhcL9b0Q-1; Thu, 05 Oct 2023 15:04:45 -0400 X-MC-Unique: C8cVV3qQOjCNR6RhcL9b0Q-1 Received: by mail-qv1-f72.google.com with SMTP id 6a1803df08f44-65b0d478deaso12831206d6.2 for ; Thu, 05 Oct 2023 12:04:45 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696532684; x=1697137484; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=6a4QN79fG24xgVpSH4QgkEr17EKa+svliYQu29U81D4=; b=sHu6IDHNGsIcA4LECz8GQc/d+YpWSGyLRN9vQ0avlgv75oD0QM4oGatWLsvKV0AGoV NtS4mcNqcZHiqnxRbE4t2/MUe2VDdCkc7ctLdLaktJeJ503tucVqA0eW+SUdEs0xmrOW Dx5MKpEWKeT1eqKIFPtfBp0q02vYjRgJ6IozpPeprQQA6/WErzZDyQQ3MOWXOOr+3PCm 8D4/2MvIHyidbd0H99b354adCr8vg2b/1Dhdfe7uh1MXfOuB5kWmruThq9d6PnKOaKZF dkaEwg9oslV6RtdQvNQpNZMIRPRpR/bu9IoQ795PjJVAf6Xe4wc1JsZcvuBLGH2l9isQ I/cg== X-Gm-Message-State: AOJu0YwNijkeX/OYYI6sDnJ/aXUZs9FDMx5llRs8FeGDF7WqlJaS5yHP DFtSqgKNPi7CzJfUozK97NCEr5nGUGIiF5sXi2Y5RtehtkM++aM9u57OxzYxs9vtezAjIimK2El /ai7kPjFaQgj22bBP8qnCTZmCkHIhAayU+HXB9V4jwMY9X72enN1QjsCD9vchqlgzG3d1jDAny1 MMRw== X-Received: by 2002:a0c:ef0d:0:b0:653:5bed:83d4 with SMTP id t13-20020a0cef0d000000b006535bed83d4mr5778145qvr.30.1696532684638; Thu, 05 Oct 2023 12:04:44 -0700 (PDT) X-Received: by 2002:a0c:ef0d:0:b0:653:5bed:83d4 with SMTP id t13-20020a0cef0d000000b006535bed83d4mr5778116qvr.30.1696532684169; Thu, 05 Oct 2023 12:04:44 -0700 (PDT) Received: from [192.168.0.174] ([104.219.124.252]) by smtp.gmail.com with ESMTPSA id u14-20020a0cf1ce000000b006560eea8a7esm708610qvl.132.2023.10.05.12.04.43 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 05 Oct 2023 12:04:43 -0700 (PDT) Message-ID: Date: Thu, 5 Oct 2023 15:04:45 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 To: gcc-patches Cc: "hernandez, aldy" From: Andrew MacLeod Subject: [COMMITTED 2/3] Add a dom based ranger for fast VRP. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1778943538115101354 X-GMAIL-MSGID: 1778943538115101354 This patch adds a DOM based ranger that is intended to be used by a dom walk pass and provides basic ranges. It utilizes the new GORI edge API to find outgoing ranges on edges, and combines these with any ranges calculated during the walk up to this point.  When a query is made for a range not defined in the current block, a quick dom walk is performed looking for a range either on a single-pred  incoming  edge or defined in the block. Its about twice the speed of current EVRP, and although there is a bit of room to improve both memory usage and speed, I'll leave that until I either get around to it or we elect to use it and it becomes more important.   It also serves as a POC for anyone wanting to use the new GORI API to use edge ranges, as well as a potentially different fast VRP more similar to the old EVRP. This version performs more folding of PHI nodes as it has all the info on incoming edges, but at a slight cost, mostly memory.  It does no relation processing as yet. It has been bootstrapped running right after EVRP, and as a replacement for EVRP, and since it uses existing machinery, should be reasonably solid.   It is currently not invoked from anywhere. Pushed. Andrew From ad8cd713b4e489826e289551b8b8f8f708293a5b Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 28 Jul 2023 13:18:15 -0400 Subject: [PATCH 2/3] Add a dom based ranger for fast VRP. Provide a dominator based implementation of a range query. * gimple_range.cc (dom_ranger::dom_ranger): New. (dom_ranger::~dom_ranger): New. (dom_ranger::range_of_expr): New. (dom_ranger::edge_range): New. (dom_ranger::range_on_edge): New. (dom_ranger::range_in_bb): New. (dom_ranger::range_of_stmt): New. (dom_ranger::maybe_push_edge): New. (dom_ranger::pre_bb): New. (dom_ranger::post_bb): New. * gimple-range.h (class dom_ranger): New. --- gcc/gimple-range.cc | 300 ++++++++++++++++++++++++++++++++++++++++++++ gcc/gimple-range.h | 28 +++++ 2 files changed, 328 insertions(+) diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 13c3308d537..5e9bb397a20 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -928,3 +928,303 @@ assume_query::dump (FILE *f) } fprintf (f, "------------------------------\n"); } + +// --------------------------------------------------------------------------- + + +// Create a DOM based ranger for use by a DOM walk pass. + +dom_ranger::dom_ranger () : m_global (), m_out () +{ + m_freelist.create (0); + m_freelist.truncate (0); + m_e0.create (0); + m_e0.safe_grow_cleared (last_basic_block_for_fn (cfun)); + m_e1.create (0); + m_e1.safe_grow_cleared (last_basic_block_for_fn (cfun)); + m_pop_list = BITMAP_ALLOC (NULL); + if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE)) + tracer.enable_trace (); +} + +// Dispose of a DOM ranger. + +dom_ranger::~dom_ranger () +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Non-varying global ranges:\n"); + fprintf (dump_file, "=========================:\n"); + m_global.dump (dump_file); + } + BITMAP_FREE (m_pop_list); + m_e1.release (); + m_e0.release (); + m_freelist.release (); +} + +// Implement range of EXPR on stmt S, and return it in R. +// Return false if no range can be calculated. + +bool +dom_ranger::range_of_expr (vrange &r, tree expr, gimple *s) +{ + unsigned idx; + if (!gimple_range_ssa_p (expr)) + return get_tree_range (r, expr, s); + + if ((idx = tracer.header ("range_of_expr "))) + { + print_generic_expr (dump_file, expr, TDF_SLIM); + if (s) + { + fprintf (dump_file, " at "); + print_gimple_stmt (dump_file, s, 0, TDF_SLIM); + } + else + fprintf (dump_file, "\n"); + } + + if (s) + range_in_bb (r, gimple_bb (s), expr); + else + m_global.range_of_expr (r, expr, s); + + if (idx) + tracer.trailer (idx, " ", true, expr, r); + return true; +} + + +// Return TRUE and the range if edge E has a range set for NAME in +// block E->src. + +bool +dom_ranger::edge_range (vrange &r, edge e, tree name) +{ + bool ret = false; + basic_block bb = e->src; + + // Check if BB has any outgoing ranges on edge E. + ssa_lazy_cache *out = NULL; + if (EDGE_SUCC (bb, 0) == e) + out = m_e0[bb->index]; + else if (EDGE_SUCC (bb, 1) == e) + out = m_e1[bb->index]; + + // If there is an edge vector and it has a range, pick it up. + if (out && out->has_range (name)) + ret = out->get_range (r, name); + + return ret; +} + + +// Return the range of EXPR on edge E in R. +// Return false if no range can be calculated. + +bool +dom_ranger::range_on_edge (vrange &r, edge e, tree expr) +{ + basic_block bb = e->src; + unsigned idx; + if ((idx = tracer.header ("range_on_edge "))) + { + fprintf (dump_file, "%d->%d for ",e->src->index, e->dest->index); + print_generic_expr (dump_file, expr, TDF_SLIM); + fputc ('\n',dump_file); + } + + if (!gimple_range_ssa_p (expr)) + return get_tree_range (r, expr, NULL); + + if (!edge_range (r, e, expr)) + range_in_bb (r, bb, expr); + + if (idx) + tracer.trailer (idx, " ", true, expr, r); + return true; +} + +// Return the range of NAME as it exists at the end of block BB in R. + +void +dom_ranger::range_in_bb (vrange &r, basic_block bb, tree name) +{ + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + // Loop through dominators until we get to the entry block, or we find + // either the defintion block for NAME, or a single pred edge with a range. + while (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)) + { + // If we hit the deifntion block, pick up the global value. + if (bb == def_bb) + { + m_global.range_of_expr (r, name); + return; + } + // If its a single pred, check the outgoing range of the edge. + if (EDGE_COUNT (bb->preds) == 1 + && edge_range (r, EDGE_PRED (bb, 0), name)) + return; + // Otherwise move up to the dominator, and check again. + bb = get_immediate_dominator (CDI_DOMINATORS, bb); + } + m_global.range_of_expr (r, name); +} + + +// Calculate the range of NAME, as the def of stmt S and return it in R. +// Return FALSE if no range cqn be calculated. +// Also set the global range for NAME as this should only be called within +// the def block during a DOM walk. +// Outgoing edges were pre-calculated, so when we establish a global defintion +// check if any outgoing edges hav ranges that can be combined with the +// global. + +bool +dom_ranger::range_of_stmt (vrange &r, gimple *s, tree name) +{ + unsigned idx; + bool ret; + if (!name) + name = gimple_range_ssa_p (gimple_get_lhs (s)); + + gcc_checking_assert (!name || name == gimple_get_lhs (s)); + + if ((idx = tracer.header ("range_of_stmt "))) + print_gimple_stmt (dump_file, s, 0, TDF_SLIM); + + // Its already been calculated. + if (name && m_global.has_range (name)) + { + ret = m_global.range_of_expr (r, name, s); + if (idx) + tracer.trailer (idx, " Already had value ", ret, name, r); + return ret; + } + + // If there is a new calculated range and it is not varying, set + // a global range. + ret = fold_range (r, s, this); + if (ret && name && m_global.merge_range (name, r) && !r.varying_p ()) + { + if (set_range_info (name, r) && dump_file) + { + fprintf (dump_file, "Global Exported: "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " = "); + r.dump (dump_file); + fputc ('\n', dump_file); + } + basic_block bb = gimple_bb (s); + unsigned bbi = bb->index; + Value_Range vr (TREE_TYPE (name)); + // If there is a range on edge 0, update it. + if (m_e0[bbi] && m_e0[bbi]->has_range (name)) + { + if (m_e0[bbi]->merge_range (name, r) && dump_file + && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Outgoing range for "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " updated on edge %d->%d : ", bbi, + EDGE_SUCC (bb, 0)->dest->index); + if (m_e0[bbi]->get_range (vr, name)) + vr.dump (dump_file); + fputc ('\n', dump_file); + } + } + // If there is a range on edge 1, update it. + if (m_e1[bbi] && m_e1[bbi]->has_range (name)) + { + if (m_e1[bbi]->merge_range (name, r) && dump_file + && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Outgoing range for "); + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, " updated on edge %d->%d : ", bbi, + EDGE_SUCC (bb, 1)->dest->index); + if (m_e1[bbi]->get_range (vr, name)) + vr.dump (dump_file); + fputc ('\n', dump_file); + } + } + } + if (idx) + tracer.trailer (idx, " ", ret, name, r); + return ret; +} + +// Check if GORI has an ranges on edge E. If there re, store them in +// either the E0 or E1 vector based on EDGE_0. +// If there are no ranges, put the empty lazy_cache entry on the freelist +// for use next time. + +void +dom_ranger::maybe_push_edge (edge e, bool edge_0) +{ + ssa_lazy_cache *e_cache; + if (!m_freelist.is_empty ()) + e_cache = m_freelist.pop (); + else + e_cache = new ssa_lazy_cache; + gori_on_edge (*e_cache, e, this, &m_out); + if (e_cache->empty_p ()) + m_freelist.safe_push (e_cache); + else + { + if (edge_0) + m_e0[e->src->index] = e_cache; + else + m_e1[e->src->index] = e_cache; + } +} + +// Preprocess block BB. If there are any outgoing edges, precalculate +// the outgoing ranges and store them. Note these are done before +// we process the block, so global values have not been set yet. +// These are "pure" outgoing ranges inflicted by the condition. + +void +dom_ranger::pre_bb (basic_block bb) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "#FVRP entering BB %d\n", bb->index); + + // Next, see if this block needs outgoing edges calculated. + gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); + if (!gsi_end_p (gsi)) + { + gimple *s = gsi_stmt (gsi); + if (is_a (s) && gimple_range_op_handler::supported_p (s)) + { + maybe_push_edge (EDGE_SUCC (bb, 0), true); + maybe_push_edge (EDGE_SUCC (bb, 1), false); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + if (m_e0[bb->index]) + { + fprintf (dump_file, "\nEdge ranges BB %d->%d\n", + bb->index, EDGE_SUCC (bb, 0)->dest->index); + m_e0[bb->index]->dump(dump_file); + } + if (m_e1[bb->index]) + { + fprintf (dump_file, "\nEdge ranges BB %d->%d\n", + bb->index, EDGE_SUCC (bb, 1)->dest->index); + m_e1[bb->index]->dump(dump_file); + } + } + } + } + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "#FVRP DONE entering BB %d\n", bb->index); +} + +// Perform any post block processing. + +void +dom_ranger::post_bb (basic_block) +{ +} diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 6587e4923ff..5807a2b80e5 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -101,5 +101,33 @@ protected: gori_compute m_gori; }; +// DOM based ranger for fast VRP. +// This must be processed in DOM order, and does only basic range operations. +class dom_ranger : public range_query +{ +public: + dom_ranger (); + ~dom_ranger (); + + virtual bool range_of_expr (vrange &r, tree expr, gimple *s = NULL) override; + virtual bool range_on_edge (vrange &r, edge e, tree expr) override; + virtual bool range_of_stmt (vrange &r, gimple *s, tree name = NULL) override; + + bool edge_range (vrange &r, edge e, tree name); + void range_in_bb (vrange &r, basic_block bb, tree name); + + void pre_bb (basic_block bb); + void post_bb (basic_block bb); +protected: + DISABLE_COPY_AND_ASSIGN (dom_ranger); + void maybe_push_edge (edge e, bool edge_0); + ssa_cache m_global; + gimple_outgoing_range m_out; + vec m_freelist; + vec m_e0; + vec m_e1; + bitmap m_pop_list; + range_tracer tracer; +}; #endif // GCC_GIMPLE_RANGE_H -- 2.41.0