From patchwork Fri Sep 17 18:20: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: 1529540 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: 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=BlYNbDJu; 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 ozlabs.org (Postfix) with ESMTPS id 4HB2NB4Pbjz9sX3 for ; Sat, 18 Sep 2021 04:21:46 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6B7503858420 for ; Fri, 17 Sep 2021 18:21:44 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6B7503858420 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1631902904; bh=rzjAmWHahwAM3zS/RziI0CQ2F7sOP/WXKmg9Y4hbhJs=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=BlYNbDJug2B8KyFZNtgjovQ77Em1rJsFF4lqmw0dTjO16FLRMfX2+bLX7Js+O1U0v BmemqXvooqReVIeY5Sp7FH5seKhzYubz82amzyedDSQPc1bmtSu5CiIBhBaQOMYfDh NNzxdFyf+UfK1Xxzy5jO+ll3Rvl5MVZ3Ny4qdsF4= 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 ESMTP id F2F99385AC19 for ; Fri, 17 Sep 2021 18:20:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F2F99385AC19 Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-21-WdVI3EdSPECWgBYVOXAIJg-1; Fri, 17 Sep 2021 14:20:08 -0400 X-MC-Unique: WdVI3EdSPECWgBYVOXAIJg-1 Received: by mail-qt1-f200.google.com with SMTP id e6-20020ac84e46000000b0029baad9aaa0so96298635qtw.11 for ; Fri, 17 Sep 2021 11:20:08 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:to:from:subject:message-id:date:user-agent :mime-version:content-language; bh=rzjAmWHahwAM3zS/RziI0CQ2F7sOP/WXKmg9Y4hbhJs=; b=lwNUVEYmtTgVK/h51WZmwLANbCkcCHsdSx9nKAoJMrGElyKkDKGLeesR5G4gndwDGB ZZAUN7+Pof62QJBtfmp0F5yauPtM2NBwaG1j/l9YCswPmPp6O3O5HQaOzaUHNTU3/kAG qXcn0LYxo9KbZcJL9QZvLXeSB31QxCWOTGq2d7DLIYQ9CL7Mj+ijwath7SkQ/Rn1Gr1l untCg2eUTFyQ0cMkKGNJf73xZg0/DooKTdZRtjuBfGtWLP0j2CqEKnQkp9+TFTfJjtuQ 7kJIzfkbvUrL5dH5iGGJnO/o1JnlHEFLU6QbkwGgHQ+6pk86lmpWL7UUiLjAo5iJn9+D B8lw== X-Gm-Message-State: AOAM532j44dQOCplnLOmot+walFtU3pZodBc4k6KvTfWBV7B9u9YSiQZ f4XC9YLgazJh9OW0VshA4AuM2DTBsTqpcrxz4sFml/bzYfsrSTSbR9g8izmL+96G30P8L58+fAn slxT4yMtCLsNtWg9TUyOCbz5u9noxo5/4LkG9iGqXH2TwWNii6t1Uw7wF1ywsGjg0KBFV6w== X-Received: by 2002:a05:620a:148c:: with SMTP id w12mr11872652qkj.71.1631902807559; Fri, 17 Sep 2021 11:20:07 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxdIsQoJ6re6XtO1R/wUAxU92SEHahnCQaqdK+RjaFOLflt5UMmC3e5HtLylQoFnLgC38NZjw== X-Received: by 2002:a05:620a:148c:: with SMTP id w12mr11872627qkj.71.1631902807257; Fri, 17 Sep 2021 11:20:07 -0700 (PDT) Received: from [192.168.0.102] ([104.219.123.55]) by smtp.gmail.com with ESMTPSA id q10sm5642640qke.108.2021.09.17.11.20.05 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 17 Sep 2021 11:20:06 -0700 (PDT) To: gcc-patches Subject: [COMMITTED] Provide a relation oracle for paths. Message-ID: <7b28ef8a-f13a-40c3-a15a-224ab5f6dd5f@redhat.com> Date: Fri, 17 Sep 2021 14:20:05 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 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, 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" This patch provides a path-oracle which complies with the relation_oracle base class and is used to track any relations that are found along a specific path. There are upcoming threader changes which utilize this oracle. As paths are walked, gimple_range_fold can be used to automatically register any relations that are discovered on this path and allowing the normal kind of relational folding to happen.  This also allows equivalencies to be entered between PHI defs and the use on the PHI edge that the path traverses. Furthermore, it can be used in conjunction with a normal ranger dominance based relation oracle which can be used to automatically utilize any relations/equivalences that are active at the start of the path an integrate seemlessly with the path relation list. Bootstrapped on x86_64-pc-linux-gnu with no regressions, pushed. Client threader code coming shortly. Andrew From 534c5352a02485a41ebfb133b42edbbecba7eba3 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Fri, 17 Sep 2021 09:48:35 -0400 Subject: [PATCH 2/2] Provide a relation oracle for paths. This provides a path_oracle class which can optionally be used in conjunction with another oracle to track relations on a path as it is walked. * value-relation.cc (class equiv_chain): Move to header file. (path_oracle::path_oracle): New. (path_oracle::~path_oracle): New. (path_oracle::register_relation): New. (path_oracle::query_relation): New. (path_oracle::reset_path): New. (path_oracle::dump): New. * value-relation.h (class equiv_chain): Move to here. (class path_oracle): New. --- gcc/value-relation.cc | 188 +++++++++++++++++++++++++++++++++++++++--- gcc/value-relation.h | 51 +++++++++++- 2 files changed, 224 insertions(+), 15 deletions(-) diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 3e077d38a11..d370f93d128 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -190,9 +190,6 @@ relation_transitive (relation_kind r1, relation_kind r2) // ------------------------------------------------------------------------- -// This class represents an equivalency set, and contains a link to the next -// one in the list to be searched. - // The very first element in the m_equiv chain is actually just a summary // element in which the m_names bitmap is used to indicate that an ssa_name // has an equivalence set in this block. @@ -201,16 +198,6 @@ relation_transitive (relation_kind r1, relation_kind r2) // which has the bit for SSA_NAME set. Then scan for the equivalency set in // that block. No previous lists need be searched. -class equiv_chain -{ -public: - bitmap m_names; // ssa-names in equiv set. - basic_block m_bb; // Block this belongs to - equiv_chain *m_next; // Next in block list. - void dump (FILE *f) const; // Show names in this list. - equiv_chain *find (unsigned ssa); -}; - // If SSA has an equivalence in this list, find and return it. // Otherwise return NULL. @@ -1172,3 +1159,178 @@ relation_oracle::debug () const { dump (stderr); } + +path_oracle::path_oracle (relation_oracle *oracle) +{ + m_root = oracle; + bitmap_obstack_initialize (&m_bitmaps); + obstack_init (&m_chain_obstack); + + // Initialize header records. + m_equiv.m_names = BITMAP_ALLOC (&m_bitmaps); + m_equiv.m_bb = NULL; + m_equiv.m_next = NULL; + m_relations.m_names = BITMAP_ALLOC (&m_bitmaps); + m_relations.m_head = NULL; +} + +path_oracle::~path_oracle () +{ + obstack_free (&m_chain_obstack, NULL); + bitmap_obstack_release (&m_bitmaps); +} + +// Return the equiv set for SSA, and if there isn't one, check for equivs +// starting in block BB. + +const_bitmap +path_oracle::equiv_set (tree ssa, basic_block bb) +{ + // Check the list first. + equiv_chain *ptr = m_equiv.find (SSA_NAME_VERSION (ssa)); + if (ptr) + return ptr->m_names; + + // Otherwise defer to the root oracle. + if (m_root) + return m_root->equiv_set (ssa, bb); + + // Allocate a throw away bitmap if there isn't a root oracle. + bitmap tmp = BITMAP_ALLOC (&m_bitmaps); + bitmap_set_bit (tmp, SSA_NAME_VERSION (ssa)); + return tmp; +} + +// Register an equivalence between SSA1 and SSA2 resolving unkowns from +// block BB. + +void +path_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) +{ + const_bitmap equiv_1 = equiv_set (ssa1, bb); + const_bitmap equiv_2 = equiv_set (ssa2, bb); + + // Check if they are the same set, if so, we're done. + if (bitmap_equal_p (equiv_1, equiv_2)) + return; + + // Don't mess around, simply create a new record and insert it first. + bitmap b = BITMAP_ALLOC (&m_bitmaps); + bitmap_copy (b, equiv_1); + bitmap_ior_into (b, equiv_2); + + equiv_chain *ptr = (equiv_chain *) obstack_alloc (&m_chain_obstack, + sizeof (equiv_chain)); + ptr->m_names = b; + ptr->m_bb = NULL; + ptr->m_next = m_equiv.m_next; + m_equiv.m_next = ptr; + bitmap_ior_into (m_equiv.m_names, b); +} + +// Register relation K between SSA1 and SSA2, resolving unknowns by +// querying from BB. + +void +path_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1, + tree ssa2) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + value_relation vr (k, ssa1, ssa2); + fprintf (dump_file, " Registering value_relation (path_oracle) "); + vr.dump (dump_file); + fprintf (dump_file, " (bb%d)\n", bb->index); + } + + if (k == EQ_EXPR) + { + register_equiv (bb, ssa1, ssa2); + return; + } + + relation_kind curr = query_relation (bb, ssa1, ssa2); + if (curr != VREL_NONE) + k = relation_intersect (curr, k); + + bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa1)); + bitmap_set_bit (m_relations.m_names, SSA_NAME_VERSION (ssa2)); + relation_chain *ptr = (relation_chain *) obstack_alloc (&m_chain_obstack, + sizeof (relation_chain)); + ptr->set_relation (k, ssa1, ssa2); + ptr->m_next = m_relations.m_head; + m_relations.m_head = ptr; +} + +// Query for a relationship between equiv set B1 and B2, resolving unknowns +// starting at block BB. + +relation_kind +path_oracle::query_relation (basic_block bb, const_bitmap b1, const_bitmap b2) +{ + if (bitmap_equal_p (b1, b2)) + return EQ_EXPR; + + relation_kind k = m_relations.find_relation (b1, b2); + + if (k == VREL_NONE && m_root) + k = m_root->query_relation (bb, b1, b2); + + return k; +} + +// Query for a relationship between SSA1 and SSA2, resolving unknowns +// starting at block BB. + +relation_kind +path_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) +{ + unsigned v1 = SSA_NAME_VERSION (ssa1); + unsigned v2 = SSA_NAME_VERSION (ssa2); + + if (v1 == v2) + return EQ_EXPR; + + const_bitmap equiv_1 = equiv_set (ssa1, bb); + const_bitmap equiv_2 = equiv_set (ssa2, bb); + if (bitmap_bit_p (equiv_1, v2) && bitmap_bit_p (equiv_2, v1)) + return EQ_EXPR; + + return query_relation (bb, equiv_1, equiv_2); +} + +// Reset any relations registered on this path. + +void +path_oracle::reset_path () +{ + m_equiv.m_next = NULL; + bitmap_clear (m_equiv.m_names); + m_relations.m_head = NULL; + bitmap_clear (m_relations.m_names); +} + +// Dump relation in basic block... Do nothing here. + +void +path_oracle::dump (FILE *, basic_block) const +{ +} + +// Dump the relations and equivalencies found in the path. + +void +path_oracle::dump (FILE *f) const +{ + equiv_chain *ptr = m_equiv.m_next; + for (; ptr; ptr = ptr->m_next) + ptr->dump (f); + + relation_chain *ptr2 = m_relations.m_head; + for (; ptr2; ptr2 = ptr2->m_next) + { + fprintf (f, "Relational : "); + ptr2->dump (f); + fprintf (f, "\n"); + } +} diff --git a/gcc/value-relation.h b/gcc/value-relation.h index 323b1e6be8d..574fdc9efe8 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -98,8 +98,18 @@ public: void debug () const; }; -// Declared internally in value-relation.cc -class equiv_chain; +// This class represents an equivalency set, and contains a link to the next +// one in the list to be searched. + +class equiv_chain +{ +public: + bitmap m_names; // ssa-names in equiv set. + basic_block m_bb; // Block this belongs to + equiv_chain *m_next; // Next in block list. + void dump (FILE *f) const; // Show names in this list. + equiv_chain *find (unsigned ssa); +}; // The equivalency oracle maintains equivalencies using the dominator tree. // Equivalencies apply to an entire basic block. Equivalencies on edges @@ -188,4 +198,41 @@ private: }; +// A path_oracle implements relations in a list. The only sense of ordering +// is the latest registered relation is the first found during a search. +// It can be constructed with an optional "root" oracle which will be used +// to look up any relations not found in the list. +// This allows the client to walk paths starting at some block and register +// and query relations along that path, ignoring other edges. +// +// For registering a relation, a query if made of the root oracle if there is +// any known relationship at block BB, and it is combined with this new +// relation and entered in the list. +// +// Queries are resolved by looking first in the list, and only if nothing is +// found is the root oracle queried at block BB. +// +// reset_path is used to clear all locally registered paths to initial state. + +class path_oracle : public relation_oracle +{ +public: + path_oracle (relation_oracle *oracle = NULL); + ~path_oracle (); + const_bitmap equiv_set (tree, basic_block); + void register_relation (basic_block, relation_kind, tree, tree); + relation_kind query_relation (basic_block, tree, tree); + relation_kind query_relation (basic_block, const_bitmap, const_bitmap); + void reset_path (); + void dump (FILE *, basic_block) const; + void dump (FILE *) const; +private: + void register_equiv (basic_block bb, tree ssa1, tree ssa2); + equiv_chain m_equiv; + relation_chain_head m_relations; + relation_oracle *m_root; + + bitmap_obstack m_bitmaps; + struct obstack m_chain_obstack; +}; #endif /* GCC_VALUE_RELATION_H */ -- 2.17.2