From patchwork Thu Oct 13 15:30:55 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 2074 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp341084wrs; Thu, 13 Oct 2022 08:32:07 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6ROYpJLIX9YnyFQofpHi0+JZqlXfwn9OvM58FJEVBMnXp9+I6Qg7t1nULvQjrpyR5kcO/w X-Received: by 2002:a50:fc85:0:b0:458:e7c6:1cfa with SMTP id f5-20020a50fc85000000b00458e7c61cfamr317398edq.256.1665675126933; Thu, 13 Oct 2022 08:32:06 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665675126; cv=none; d=google.com; s=arc-20160816; b=JZt74A10TekknSaMWRRCCZaQ0bI1S47IQAfzeb8tplFf1Po7oq57ByHL50ITPlN7/5 7WsgU8ohRkmllRqWpmbpGoVnojkRaaYZV7udLcYEO5WgXq1JCBdVunwETt60TGyebdFD l7naIG+jkjR/jK7S2wMLjw+sI05lgKyJGCKMS6veXvmaP1UwE8uZT8VAqoF37A2HypBc VkpVh/IDRNWXYYcbeGZIujXIsvxzos8N8e29kEw1UK11T2FhYb7FDx/BlUnVdtWDXVmh HDhC18eZmlILZsmSsmyZAdNTcp3xutcke1it3xuVtTARhQLw+FS1YYteO090OsjKTTa4 cjpg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:content-language :subject:to:user-agent:mime-version:date:message-id:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=sW/gYUrlawUVl1s6yjjfYWzkla69td0Dc90dhqHKA4E=; b=BhN+4HsA+T7jQ3hpFDe9c7YP6Icmdtb3fmV/Mo42xo2x3vHt+kP6jGsqA030aFS7Qc KAZiSk5STEbl676wr/fgo3xq70VdOi9XuelyVAWmWhyXTnmJ8pJP8PUZLDKOBwUX3OsF h7WtDGWOzPgzF0UgrwPOIJC+fOKUMn1KuzbqbWqPjDYVmlIggC32e5MeDs+ko/7fDzmo gd24yRaQZQ7F8M9EKkodrZlMfJBn+Ub//FYnMGmsmO3I0L/2I/9YlHBtZDJHiVBmRlTn Xbnxut7cF1gL4Hj56e2Dfa4mrBxzaanFrQSSSEsAkFgg7iShqaUOlqLrci9GupV2NsHY Q92A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="EtQ9dDx/"; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id l15-20020a056402028f00b00459cbb8074asi14740edv.439.2022.10.13.08.32.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 13 Oct 2022 08:32:06 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="EtQ9dDx/"; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C01ED3850864 for ; Thu, 13 Oct 2022 15:31:46 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C01ED3850864 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1665675106; bh=sW/gYUrlawUVl1s6yjjfYWzkla69td0Dc90dhqHKA4E=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=EtQ9dDx/IR0vD5dFbu0PU3DWEZ5LK/nGq2b+2bA4QokvHaXuZMmA4ELizSuIJ9AUF TPqk6mJCfksiJ4ZUD3kXae1RieHM8+L1GiyUe4YX5KgiEWJ5tNgF0Qf9JLhmm32+aJ 0v+N8Dhjm/CIVRvPUfgs1TtpyRkNIYc7Xf5cR3IY= 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 DE47B3856DC3 for ; Thu, 13 Oct 2022 15:31:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DE47B3856DC3 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.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-10-1G2ax6iPONyJ3WvJgyEssA-1; Thu, 13 Oct 2022 11:30:59 -0400 X-MC-Unique: 1G2ax6iPONyJ3WvJgyEssA-1 Received: by mail-qt1-f198.google.com with SMTP id bv21-20020a05622a0a1500b00393a6724d4cso1552205qtb.23 for ; Thu, 13 Oct 2022 08:30:58 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; 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=B0fmdpW/AHa+kEUt4IyswpaL3sus9BHHp58tNocHyCQ=; b=bTpC8Ua4Ts+EhjhFhkYFMqJeRO2d6+p+iX21vJLgRPYW03tU0aQ5qd6bb6HOdSJTVI ViIaHhOe1Su/cGd/SZ4Om2Mi+4sh7IeGLYc+AxWKiuMNCG9Dud9x4N2hLDrY7beZ+fr8 9x7JhUeSZxMyMDldEI/0NtqqGmUE3lRbcNa2s66Gz3DmAec481tD/TUdyvDx5thPFhVQ NqFcgoXIYarKqSLHp4oVcuGC2pC9loxb0fbIovPjha6fyEYhdNutNa33DXcLGst6W2GG /mKlV78IK6Car8BZJjpXHJDmC7V5i4CFExcNTmv6nUDvg4PVmfa95FG3t7D2KatqHCkL 5xyg== X-Gm-Message-State: ACrzQf2IEaQ4BHW2qD8dgYV9PkIcYepbGIETNfY8Q5xq5QS4loatsH36 mVDlUYSWiaJwvHU+0252fXDnHT4PNpdnJedk3ycZcO0hhqDRk27RLW6Fv8qVD9w1rReyZ/MtTTi HqqeNse6tqIiidtuqOoYRwf9qBI76D9F+Pnq5hq0ljJ+e41BrzX8ytK2kbiVBmLnDWRINDQ== X-Received: by 2002:a05:622a:492:b0:35d:518d:2b58 with SMTP id p18-20020a05622a049200b0035d518d2b58mr365399qtx.78.1665675057567; Thu, 13 Oct 2022 08:30:57 -0700 (PDT) X-Received: by 2002:a05:622a:492:b0:35d:518d:2b58 with SMTP id p18-20020a05622a049200b0035d518d2b58mr365371qtx.78.1665675057251; Thu, 13 Oct 2022 08:30:57 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::50d4? ([2607:fea8:a263:f600::50d4]) by smtp.gmail.com with ESMTPSA id t13-20020a05620a450d00b006ec62032d3dsm17596qkp.30.2022.10.13.08.30.55 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 13 Oct 2022 08:30:56 -0700 (PDT) Message-ID: <70c3023e-cbc0-312b-431b-7fd8eda37e74@redhat.com> Date: Thu, 13 Oct 2022 11:30:55 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.1 To: gcc-patches Subject: [COMMITTED 2/4] Add equivalence iterator to relation oracle. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.4 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, 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.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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746586961875281968?= X-GMAIL-MSGID: =?utf-8?q?1746586961875281968?= Instead of looping over an exposed equivalence bitmap, provide iterators to loop over equivalences, partial equivalences, or both. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed Andrew From aa05838b0536422256e0c477c57f1ea1d2915e92 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 7 Oct 2022 12:55:32 -0400 Subject: [PATCH 2/4] Add equivalence iterator to relation oracle. Instead of looping over an exposed equivalence bitmap, provide iterators to loop over equivalences, partial equivalences, or both. * gimple-range-cache.cc (ranger_cache::fill_block_cache): Use iterator. * value-relation.cc (equiv_relation_iterator::equiv_relation_iterator): New. (equiv_relation_iterator::next): New. (equiv_relation_iterator::get_name): New. * value-relation.h (class relation_oracle): Privatize some methods. (class equiv_relation_iterator): New. (FOR_EACH_EQUIVALENCE): New. (FOR_EACH_PARTIAL_EQUIV): New. (FOR_EACH_PARTIAL_AND_FULL_EQUIV): New. --- gcc/gimple-range-cache.cc | 10 +---- gcc/value-relation.cc | 78 +++++++++++++++++++++++++++++++++++++++ gcc/value-relation.h | 41 ++++++++++++++++++-- 3 files changed, 118 insertions(+), 11 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 4782d47265e..8c80ba6cd14 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1220,15 +1220,9 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) // See if any equivalences can refine it. if (m_oracle) { - unsigned i; - bitmap_iterator bi; - // Query equivalences in read-only mode. - const_bitmap equiv = m_oracle->equiv_set (name, bb); - EXECUTE_IF_SET_IN_BITMAP (equiv, 0, i, bi) + tree equiv_name; + FOR_EACH_EQUIVALENCE (m_oracle, bb, name, equiv_name) { - if (i == SSA_NAME_VERSION (name)) - continue; - tree equiv_name = ssa_name (i); basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name)); // Check if the equiv has any ranges calculated. diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index ceeca53e0a1..50fc190a36b 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -1641,3 +1641,81 @@ path_oracle::dump (FILE *f) const fprintf (f, "\n"); } } + +// ------------------------------------------------------------------------ +// EQUIV iterator. Although we have bitmap iterators, don't expose that it +// is currently a bitmap. Use an export iterator to hide future changes. + +// Construct a basic iterator over an equivalence bitmap. + +equiv_relation_iterator::equiv_relation_iterator (relation_oracle *oracle, + basic_block bb, tree name, + bool full, bool partial) +{ + m_name = name; + m_oracle = oracle; + m_pe = partial ? oracle->partial_equiv_set (name) : NULL; + m_bm = NULL; + if (full) + m_bm = oracle->equiv_set (name, bb); + if (!m_bm && m_pe) + m_bm = m_pe->members; + if (m_bm) + bmp_iter_set_init (&m_bi, m_bm, 1, &m_y); +} + +// Move to the next export bitmap spot. + +void +equiv_relation_iterator::next () +{ + bmp_iter_next (&m_bi, &m_y); +} + +// Fetch the name of the next export in the export list. Return NULL if +// iteration is done. + +tree +equiv_relation_iterator::get_name (relation_kind *rel) +{ + if (!m_bm) + return NULL_TREE; + + while (bmp_iter_set (&m_bi, &m_y)) + { + // Do not return self. + tree t = ssa_name (m_y); + if (t && t != m_name) + { + relation_kind k = VREL_EQ; + if (m_pe && m_bm == m_pe->members) + { + const pe_slice *equiv_pe = m_oracle->partial_equiv_set (t); + if (equiv_pe && equiv_pe->members == m_pe->members) + k = pe_min (m_pe->code, equiv_pe->code); + else + k = VREL_VARYING; + } + if (relation_equiv_p (k)) + { + if (rel) + *rel = k; + return t; + } + } + next (); + } + + // Process partial equivs after full equivs if both were requested. + if (m_pe && m_bm != m_pe->members) + { + m_bm = m_pe->members; + if (m_bm) + { + // Recursively call back to process First PE. + bmp_iter_set_init (&m_bi, m_bm, 1, &m_y); + return get_name (rel); + } + } + return NULL_TREE; +} diff --git a/gcc/value-relation.h b/gcc/value-relation.h index f5f2524ad56..a3bbe1e8157 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -100,9 +100,6 @@ public: // register a relation between 2 ssa names on an edge. void register_edge (edge, relation_kind, tree, tree); - // Return equivalency set for an SSA name in a basic block. - virtual const_bitmap equiv_set (tree, basic_block) = 0; - virtual const class pe_slice *partial_equiv_set (tree) { return NULL; } // register a relation between 2 ssa names in a basic block. virtual void register_relation (basic_block, relation_kind, tree, tree) = 0; // Query for a relation between two ssa names in a basic block. @@ -115,6 +112,11 @@ public: virtual void dump (FILE *) const = 0; void debug () const; protected: + friend class equiv_relation_iterator; + // Return equivalency set for an SSA name in a basic block. + virtual const_bitmap equiv_set (tree, basic_block) = 0; + // Return partial equivalency record for an SSA name. + virtual const class pe_slice *partial_equiv_set (tree) { return NULL; } void valid_equivs (bitmap b, const_bitmap equivs, basic_block bb); // Query for a relation between two equivalency sets in a basic block. virtual relation_kind query_relation (basic_block, const_bitmap, @@ -281,6 +283,39 @@ private: struct obstack m_chain_obstack; }; +// Used to assist with iterating over the equivalence list. +class equiv_relation_iterator { +public: + equiv_relation_iterator (relation_oracle *oracle, basic_block bb, tree name, + bool full = true, bool partial = false); + void next (); + tree get_name (relation_kind *rel = NULL); +protected: + relation_oracle *m_oracle; + const_bitmap m_bm; + const pe_slice *m_pe; + bitmap_iterator m_bi; + unsigned m_y; + tree m_name; +}; + +#define FOR_EACH_EQUIVALENCE(oracle, bb, name, equiv_name) \ + for (equiv_relation_iterator iter (oracle, bb, name, true, false); \ + ((equiv_name) = iter.get_name ()); \ + iter.next ()) + +#define FOR_EACH_PARTIAL_EQUIV(oracle, bb, name, equiv_name, equiv_rel) \ + for (equiv_relation_iterator iter (oracle, bb, name, false, true); \ + ((equiv_name) = iter.get_name (&equiv_rel)); \ + iter.next ()) + +#define FOR_EACH_PARTIAL_AND_FULL_EQUIV(oracle, bb, name, equiv_name, \ + equiv_rel) \ + for (equiv_relation_iterator iter (oracle, bb, name, true, true); \ + ((equiv_name) = iter.get_name (&equiv_rel)); \ + iter.next ()) + + // The value-relation class is used to encapsulate the represention of an // individual relation between 2 ssa-names, and to facilitate operating on // the relation. -- 2.37.3