From patchwork Fri Sep 17 18:19:37 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 45140 X-Patchwork-Delegate: jwakely.gcc@gmail.com 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 603B43857C75 for ; Fri, 17 Sep 2021 18:20:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 603B43857C75 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1631902824; bh=Kuq/zs2t7MuGjvwmEe/eqBzjfcgVGCFVz7huhzWPE9U=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=iYdWD1Ew6rkAmTAFf95FUve81tSIUbc3a9IRwt2mNPeJ63FVMHBgWPhpZYCyr+gu1 kdSQqeOgXa5s4hUt/ZcozYz5U7aJZIvdhCshr7iGUHn8DO9HI6Rz3VY+p7rEDL+ob6 YBudYvH2ePctsmAqk2nc9ALN+DLN2g66jMy4e+Ok= 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 ESMTP id 323893858420 for ; Fri, 17 Sep 2021 18:19:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 323893858420 Received: from mail-qv1-f71.google.com (mail-qv1-f71.google.com [209.85.219.71]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-244-tlzak0p6PaeSpwQOKKWVsA-1; Fri, 17 Sep 2021 14:19:49 -0400 X-MC-Unique: tlzak0p6PaeSpwQOKKWVsA-1 Received: by mail-qv1-f71.google.com with SMTP id z6-20020a056214060600b0037a3f6bd9abso98756030qvw.3 for ; Fri, 17 Sep 2021 11:19:49 -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=Kuq/zs2t7MuGjvwmEe/eqBzjfcgVGCFVz7huhzWPE9U=; b=BEFNaVowc5ffBR3/1/F8hge5ChawH0qpYpQGWO+l/h4efvWFwS9RbCLTPZZhorSEry q0kr2HRkcnsjAG28CXiOntMXlCo8OysVq1aEDbJpezxmDua14/SzCcqz5RcLshVfklh7 H1s3PKCX1gTSyvamcEWtnxfma3QEb+YPpC+eoz9AFk2paDwGJTKb4rdjG6yCpgO9CwZs uv1yuPi6RDI0CNdPi6rloDFRThqSPzpNkwHiFLMEi0D5lAl3/iBcvCl4S2zlybWocOLS QsFOWJKmnaxsyPPV+5XH5ubXRcR2UPJ/HFwNC2al/8s+Ig41apvtEWU3n7CH3YIQjgJT ie3w== X-Gm-Message-State: AOAM531XyNof1z3OIirYDMXwB65luzA6SAIXQcikYbBaxlwlzKZzo+tx V9xTaKnIU0+B1O8ajOAVUj2OUO5LZWZxZXpRzIXqiofSHaZC5hqzkCxdsD/Nduic6hq/TxOWKso PkBzR1XTDWHuX20bEozNfnspncmTbyRKSHs8g3NZfz3rrUl6oBMvo1ZnXGltcTnnoLU5AXg== X-Received: by 2002:a0c:9d82:: with SMTP id s2mr12393286qvd.23.1631902788576; Fri, 17 Sep 2021 11:19:48 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwt/14vfViqXEPULh2CHQ1IrSgoyLsPFDoKdp9Ve/xxEEPX8szHxft467evl/joMhb8DR4YUA== X-Received: by 2002:a0c:9d82:: with SMTP id s2mr12393262qvd.23.1631902788284; Fri, 17 Sep 2021 11:19:48 -0700 (PDT) Received: from [192.168.0.102] ([104.219.123.55]) by smtp.gmail.com with ESMTPSA id j184sm5495407qkd.74.2021.09.17.11.19.44 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 17 Sep 2021 11:19:47 -0700 (PDT) To: gcc-patches Subject: [COMMITTED] Virtualize relation oracle and various cleanups. Message-ID: <0ccf588c-62ce-80c9-5f02-1c23cbc6191d@redhat.com> Date: Fri, 17 Sep 2021 14:19:37 -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.1 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 patch cleans up a number of things in the relation oracle. First it virtualizes a base relation_oracle class, and then standardizes the equivalency oracle to utilize that API, and then restructures the old relation oracle into a dominance based oracle which inherits from the equivalency oracle.  This simplifies some of the code, and paves the way for a the next patch which provides a path-based oracle which the threader will use to maintain relations on paths. The only externally functional change is the requirements for equivalence have been tightened up slightly such that we will not report an equivalence if each ssa name is not in the other's equivalence set.  There is a forthcoming path which firms this up even more, but this is enough for the moment. Bootstrapped on x86_64-pc-linux-gnu with no regressions, pushed. Andrew From 3674d8e6fc6305507ed50b501f049f25f868458a Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 15 Sep 2021 14:43:51 -0400 Subject: [PATCH 1/2] Virtualize relation oracle and various cleanups. Standardize equiv_oracle API onto the new relation_oracle virtual base, and then have dom_oracle inherit from that. equiv_set always returns an equivalency set now, never NULL. EQ_EXPR requires symmetry now. Each SSA name must be in the other equiv set. Shuffle some routines around, simplify. * gimple-range-cache.cc (ranger_cache::ranger_cache): Create a DOM based oracle. * gimple-range-fold.cc (fur_depend::register_relation): Use register_stmt/edge routines. * value-relation.cc (equiv_chain::find): Relocate from equiv_oracle. (equiv_oracle::equiv_oracle): Create self equivalence cache. (equiv_oracle::~equiv_oracle): Release same. (equiv_oracle::equiv_set): Return entry from self equiv cache if there are no equivalences. (equiv_oracle::find_equiv_block): Move list find to equiv_chain. (equiv_oracle::register_relation): Rename from register_equiv. (relation_chain_head::find_relation): Relocate from dom_oracle. (relation_oracle::register_stmt): New. (relation_oracle::register_edge): New. (dom_oracle::*): Rename from relation_oracle. (dom_oracle::register_relation): Adjust to call equiv_oracle. (dom_oracle::set_one_relation): Split from register_relation. (dom_oracle::register_transitives): Consolidate 2 methods. (dom_oracle::find_relation_block): Move core to relation_chain. (dom_oracle::query_relation): Rename from find_relation_dom and adjust. * value-relation.h (class relation_oracle): New pure virtual base. (class equiv_oracle): Inherit from relation_oracle and adjust. (class dom_oracle): Rename from old relation_oracle and adjust. --- gcc/gimple-range-cache.cc | 2 +- gcc/gimple-range-fold.cc | 4 +- gcc/value-relation.cc | 316 +++++++++++++++++++------------------- gcc/value-relation.h | 62 +++++--- 4 files changed, 206 insertions(+), 178 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index facf981c15d..fbf0f95eef9 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -760,7 +760,7 @@ ranger_cache::ranger_cache () m_temporal = new temporal_cache; // If DOM info is available, spawn an oracle as well. if (dom_info_available_p (CDI_DOMINATORS)) - m_oracle = new relation_oracle (); + m_oracle = new dom_oracle (); else m_oracle = NULL; diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 7cf8830fc5d..997d02dd4b9 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -195,7 +195,7 @@ void fur_depend::register_relation (gimple *s, relation_kind k, tree op1, tree op2) { if (m_oracle) - m_oracle->register_relation (s, k, op1, op2); + m_oracle->register_stmt (s, k, op1, op2); } // Register a relation on an edge if there is an oracle. @@ -204,7 +204,7 @@ void fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2) { if (m_oracle) - m_oracle->register_relation (e, k, op1, op2); + m_oracle->register_edge (e, k, op1, op2); } // This version of fur_source will pick a range up from a list of ranges diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index ba01d298521..3e077d38a11 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -199,7 +199,7 @@ relation_transitive (relation_kind r1, relation_kind r2) // This allows for much faster traversal of the DOM chain, as a search for // SSA_NAME simply requires walking the DOM chain until a block is found // which has the bit for SSA_NAME set. Then scan for the equivalency set in -// that block. No previous blcoks need be searched. +// that block. No previous lists need be searched. class equiv_chain { @@ -208,8 +208,26 @@ public: 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. + +equiv_chain * +equiv_chain::find (unsigned ssa) +{ + equiv_chain *ptr = NULL; + // If there are equiv sets and SSA is in one in this list, find it. + // Otherwise return NULL. + if (bitmap_bit_p (m_names, ssa)) + { + for (ptr = m_next; ptr; ptr = ptr->m_next) + if (bitmap_bit_p (ptr->m_names, ssa)) + break; + } + return ptr; +} // Dump the names in this equivalence set. @@ -244,12 +262,15 @@ equiv_oracle::equiv_oracle () m_equiv.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); m_equiv_set = BITMAP_ALLOC (&m_bitmaps); obstack_init (&m_chain_obstack); + m_self_equiv.create (0); + m_self_equiv.safe_grow_cleared (num_ssa_names + 1); } // Destruct an equivalency oracle. equiv_oracle::~equiv_oracle () { + m_self_equiv.release (); obstack_free (&m_chain_obstack, NULL); m_equiv.release (); bitmap_obstack_release (&m_bitmaps); @@ -259,16 +280,48 @@ equiv_oracle::~equiv_oracle () // This is the external API. const_bitmap -equiv_oracle::equiv_set (tree ssa, basic_block bb) const +equiv_oracle::equiv_set (tree ssa, basic_block bb) { // Search the dominator tree for an equivalency. equiv_chain *equiv = find_equiv_dom (ssa, bb); if (equiv) return equiv->m_names; - return NULL; + // Otherwise return a cached equiv set containing just this SSA. + unsigned v = SSA_NAME_VERSION (ssa); + if (v >= m_self_equiv.length ()) + m_self_equiv.safe_grow_cleared (num_ssa_names + 1); + + if (!m_self_equiv[v]) + { + m_self_equiv[v] = BITMAP_ALLOC (&m_bitmaps); + bitmap_set_bit (m_self_equiv[v], v); + } + return m_self_equiv[v]; } +// Query if thre is a relation (equivalence) between 2 SSA_NAMEs. + +relation_kind +equiv_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) +{ + // If the 2 ssa names share the same equiv set, they are equal. + if (equiv_set (ssa1, bb) == equiv_set (ssa2, bb)) + return EQ_EXPR; + return VREL_NONE; +} + +// Query if thre is a relation (equivalence) between 2 SSA_NAMEs. + +relation_kind +equiv_oracle::query_relation (basic_block bb ATTRIBUTE_UNUSED, const_bitmap e1, + const_bitmap e2) +{ + // If the 2 ssa names share the same equiv set, they are equal. + if (bitmap_equal_p (e1, e2)) + return EQ_EXPR; + return VREL_NONE; +} // If SSA has an equivalence in block BB, find and return it. // Otherwise return NULL. @@ -276,19 +329,10 @@ equiv_oracle::equiv_set (tree ssa, basic_block bb) const equiv_chain * equiv_oracle::find_equiv_block (unsigned ssa, int bb) const { - equiv_chain *ptr = NULL; - if (bb >= (int)m_equiv.length ()) + if (bb >= (int)m_equiv.length () || !m_equiv[bb]) return NULL; - // If there are equiv sets and SSA is in one in this block, find it. - // Otherwise return NULL. - if (m_equiv[bb] && bitmap_bit_p (m_equiv[bb]->m_names, ssa)) - { - for (ptr = m_equiv[bb]->m_next; ptr; ptr = ptr->m_next) - if (bitmap_bit_p (ptr->m_names, ssa)) - break; - } - return ptr; + return m_equiv[bb]->find (ssa); } // Starting at block BB, walk the dominator chain looking for the nearest @@ -385,8 +429,13 @@ equiv_oracle::register_equiv (basic_block bb, equiv_chain *equiv_1, // containing all the ssa_names in this basic block. void -equiv_oracle::register_equiv (basic_block bb, tree ssa1, tree ssa2) +equiv_oracle::register_relation (basic_block bb, relation_kind k, tree ssa1, + tree ssa2) { + // Only handle equality relations. + if (k != EQ_EXPR) + return; + unsigned v1 = SSA_NAME_VERSION (ssa1); unsigned v2 = SSA_NAME_VERSION (ssa2); equiv_chain *equiv_1 = find_equiv_dom (ssa1, bb); @@ -681,9 +730,37 @@ public: // ------------------------------------------------------------------------ +// Find the relation between any ssa_name in B1 and any name in B2 in LIST. +// This will allow equivalencies to be applied to any SSA_NAME in a relation. + +relation_kind +relation_chain_head::find_relation (const_bitmap b1, const_bitmap b2) const +{ + if (!m_names) + return VREL_NONE; + + // If both b1 and b2 aren't referenced in thie block, cant be a relation + if (!bitmap_intersect_p (m_names, b1) || !bitmap_intersect_p (m_names, b2)) + return VREL_NONE; + + // Search for the fiorst relation that contains BOTH an element from B1 + // and B2, and return that relation. + for (relation_chain *ptr = m_head; ptr ; ptr = ptr->m_next) + { + unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); + unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); + if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2)) + return ptr->kind (); + if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1)) + return relation_swap (ptr->kind ()); + } + + return VREL_NONE; +} + // Instantiate a relation oracle. -relation_oracle::relation_oracle () +dom_oracle::dom_oracle () { m_relations.create (0); m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1); @@ -694,7 +771,7 @@ relation_oracle::relation_oracle () // Destruct a relation oracle. -relation_oracle::~relation_oracle () +dom_oracle::~dom_oracle () { m_relations.release (); } @@ -702,8 +779,8 @@ relation_oracle::~relation_oracle () // Register relation K between ssa_name OP1 and OP2 on STMT. void -relation_oracle::register_relation (gimple *stmt, relation_kind k, tree op1, - tree op2) +relation_oracle::register_stmt (gimple *stmt, relation_kind k, tree op1, + tree op2) { gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); @@ -722,19 +799,13 @@ relation_oracle::register_relation (gimple *stmt, relation_kind k, tree op1, print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } - // This relation applies to the entire block, use STMT's block. - // Equivalencies are handled by the equivalence oracle. - if (k == EQ_EXPR) - register_equiv (gimple_bb (stmt), op1, op2); - else - register_relation (gimple_bb (stmt), k, op1, op2); + register_relation (gimple_bb (stmt), k, op1, op2); } // Register relation K between ssa_name OP1 and OP2 on edge E. void -relation_oracle::register_relation (edge e, relation_kind k, tree op1, - tree op2) +relation_oracle::register_edge (edge e, relation_kind k, tree op1, tree op2) { gcc_checking_assert (TREE_CODE (op1) == SSA_NAME); gcc_checking_assert (TREE_CODE (op2) == SSA_NAME); @@ -752,24 +823,35 @@ relation_oracle::register_relation (edge e, relation_kind k, tree op1, fprintf (dump_file, " on (%d->%d)\n", e->src->index, e->dest->index); } - // Equivalencies are handled by the equivalence oracle. + register_relation (e->dest, k, op1, op2); +} + +// Register relation K between OP! and OP2 in block BB. +// This creates the record and searches for existing records in the dominator +// tree to merge with. + +void +dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1, + tree op2) +{ // Equivalencies are handled by the equivalence oracle. if (k == EQ_EXPR) - register_equiv (e->dest, op1, op2); + equiv_oracle::register_relation (bb, k, op1, op2); else - register_relation (e->dest, k, op1, op2); + { + relation_chain *ptr = set_one_relation (bb, k, op1, op2); + register_transitives (bb, *ptr); + } } // Register relation K between OP! and OP2 in block BB. // This creates the record and searches for existing records in the dominator // tree to merge with. -// TRANSITIVE_P is true if this is being registered as a transitive operation, -// and should not try to register further transitives. -void -relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1, - tree op2, bool transitive_p) +relation_chain * +dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1, + tree op2) { - gcc_checking_assert (k != VREL_NONE); + gcc_checking_assert (k != VREL_NONE && k != EQ_EXPR); value_relation vr(k, op1, op2); int bbi = bb->index; @@ -824,11 +906,9 @@ relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1, sizeof (relation_chain)); ptr->set_relation (k, op1, op2); ptr->m_next = m_relations[bbi].m_head; - m_relations[bbi].m_head = ptr;; + m_relations[bbi].m_head = ptr; } - - if (!transitive_p) - register_transitives (bb, *ptr); + return ptr; } // Starting at ROOT_BB search the DOM tree looking for relations which @@ -837,12 +917,25 @@ relation_oracle::register_relation (basic_block bb, relation_kind k, tree op1, // considered. void -relation_oracle::register_transitives (basic_block root_bb, - const value_relation &relation, - const_bitmap equiv1, - const_bitmap equiv2) +dom_oracle::register_transitives (basic_block root_bb, + const value_relation &relation) { basic_block bb; + // Only apply transitives to certain kinds of operations. + switch (relation.kind ()) + { + case LE_EXPR: + case LT_EXPR: + case GT_EXPR: + case GE_EXPR: + break; + default: + return; + } + + const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb); + const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb); + for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb)) { int bbi = bb->index; @@ -897,8 +990,7 @@ relation_oracle::register_transitives (basic_block root_bb, value_relation nr (relation.kind (), r1, r2); if (nr.apply_transitive (*ptr)) { - register_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 (), - true); + set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " Registering transitive relation "); @@ -911,98 +1003,30 @@ relation_oracle::register_transitives (basic_block root_bb, } } -// Find adn register any transitive relations implied by RELATION occuring -// in block BB. - -void -relation_oracle::register_transitives (basic_block bb, - const value_relation &relation) -{ - // Only apply transitives to certain kinds of operations. - switch (relation.kind ()) - { - case LE_EXPR: - case LT_EXPR: - case GT_EXPR: - case GE_EXPR: - break; - default: - return; - } - - // Set up the bitmaps for op1 and op2, and if there are no equivalencies, - // set just op1 or op2 in their own bitmap. - const_bitmap equiv1 = equiv_set (relation.op1 (), bb); - const_bitmap equiv2 = equiv_set (relation.op2 (), bb); - if (equiv1) - { - if (equiv2) - register_transitives (bb, relation, equiv1, equiv2); - else - { - bitmap_clear (m_tmp); - bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op2 ())); - register_transitives (bb, relation, equiv1, m_tmp); - } - } - else if (equiv2) - { - bitmap_clear (m_tmp); - bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op1 ())); - register_transitives (bb, relation, m_tmp, equiv2); - } - else - { - bitmap_clear (m_tmp); - bitmap_clear (m_tmp2); - bitmap_set_bit (m_tmp, SSA_NAME_VERSION (relation.op1 ())); - bitmap_set_bit (m_tmp2, SSA_NAME_VERSION (relation.op2 ())); - register_transitives (bb, relation, m_tmp, m_tmp2); - } -} - // Find the relation between any ssa_name in B1 and any name in B2 in block BB. // This will allow equivalencies to be applied to any SSA_NAME in a relation. relation_kind -relation_oracle::find_relation_block (unsigned bb, const_bitmap b1, - const_bitmap b2) +dom_oracle::find_relation_block (unsigned bb, const_bitmap b1, + const_bitmap b2) const { - const_bitmap bm; if (bb >= m_relations.length()) return VREL_NONE; - bm = m_relations[bb].m_names; - if (!bm) - return VREL_NONE; - - // If both b1 and b2 aren't referenced in thie block, cant be a relation - if (!bitmap_intersect_p (bm, b1) || !bitmap_intersect_p (bm, b2)) - return VREL_NONE; - - // Search for the fiorst relation that contains BOTH an element from B1 - // and B2, and return that relation. - for (relation_chain *ptr = m_relations[bb].m_head; ptr ; ptr = ptr->m_next) - { - unsigned op1 = SSA_NAME_VERSION (ptr->op1 ()); - unsigned op2 = SSA_NAME_VERSION (ptr->op2 ()); - if (bitmap_bit_p (b1, op1) && bitmap_bit_p (b2, op2)) - return ptr->kind (); - if (bitmap_bit_p (b1, op2) && bitmap_bit_p (b2, op1)) - return relation_swap (ptr->kind ()); - } - - return VREL_NONE; + return m_relations[bb].find_relation (b1, b2); } -// Search the DOM tree for a relation between an element of B1 and B2, starting -// with block BB. +// Search the DOM tree for a relation between an element of equivalency set B1 +// and B2, starting with block BB. relation_kind -relation_oracle::find_relation_dom (basic_block bb, const_bitmap b1, - const_bitmap b2) +dom_oracle::query_relation (basic_block bb, const_bitmap b1, + const_bitmap b2) { relation_kind r; + if (bitmap_equal_p (b1, b2)) + return EQ_EXPR; + // If either name does not occur in a relation anywhere, there isnt one. if (!bitmap_intersect_p (m_relation_set, b1) || !bitmap_intersect_p (m_relation_set, b2)) @@ -1023,8 +1047,8 @@ relation_oracle::find_relation_dom (basic_block bb, const_bitmap b1, // is found, return a pointer to the chain object in OBJ. relation_kind -relation_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, - relation_chain **obj) +dom_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, + relation_chain **obj) const { if (bb >= (int)m_relations.length()) return VREL_NONE; @@ -1063,7 +1087,7 @@ relation_oracle::find_relation_block (int bb, unsigned v1, unsigned v2, // starting with block BB relation_kind -relation_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) +dom_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const { relation_kind r; // IF either name does not occur in a relation anywhere, there isnt one. @@ -1084,7 +1108,7 @@ relation_oracle::find_relation_dom (basic_block bb, unsigned v1, unsigned v2) // dominator of BB relation_kind -relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) +dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) { relation_kind kind; unsigned v1 = SSA_NAME_VERSION (ssa1); @@ -1092,9 +1116,10 @@ relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) if (v1 == v2) return EQ_EXPR; - // Check for equivalence first. + // Check for equivalence first. They must be in each equivalency set. const_bitmap equiv1 = equiv_set (ssa1, bb); - if (equiv1 && bitmap_bit_p (equiv1, v2)) + const_bitmap equiv2 = equiv_set (ssa2, bb); + if (bitmap_bit_p (equiv1, v2) && bitmap_bit_p (equiv2, v1)) return EQ_EXPR; // Initially look for a direct relationship and just return that. @@ -1102,38 +1127,15 @@ relation_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) if (kind != VREL_NONE) return kind; - // If v2 isn't in v1s equiv set, then v1 shouldn't be in v2's set either. - // It is possible for out-of-order dominator processing to have an out of - // sync set of equivalences.. Down the road, when we do full updates, - // change this to an assert to ensure everything is in sync. - const_bitmap equiv2 = equiv_set (ssa2, bb); - if (equiv2 && bitmap_bit_p (equiv2, v1)) - return EQ_EXPR; - - // If not equal, see if there is a relationship between equivalences. - if (!equiv1 && !equiv2) - kind = VREL_NONE; - else if (!equiv1) - { - bitmap_clear (m_tmp); - bitmap_set_bit (m_tmp, v1); - kind = find_relation_dom (bb, m_tmp, equiv2); - } - else if (!equiv2) - { - bitmap_clear (m_tmp); - bitmap_set_bit (m_tmp, v2); - kind = find_relation_dom (bb, equiv1, m_tmp); - } - else - kind = find_relation_dom (bb, equiv1, equiv2); + // Query using the equiovalence sets. + kind = query_relation (bb, equiv1, equiv2); return kind; } // Dump all the relations in block BB to file F. void -relation_oracle::dump (FILE *f, basic_block bb) const +dom_oracle::dump (FILE *f, basic_block bb) const { equiv_oracle::dump (f,bb); @@ -1154,7 +1156,7 @@ relation_oracle::dump (FILE *f, basic_block bb) const // Dump all the relations known to file F. void -relation_oracle::dump (FILE *f) const +dom_oracle::dump (FILE *f) const { fprintf (f, "Relation dump\n"); for (unsigned i = 0; i < m_relations.length (); i++) diff --git a/gcc/value-relation.h b/gcc/value-relation.h index 27158e051bf..323b1e6be8d 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -73,6 +73,31 @@ relation_kind relation_negate (relation_kind r); relation_kind relation_swap (relation_kind r); void print_relation (FILE *f, relation_kind rel); + +class relation_oracle +{ +public: + virtual ~relation_oracle () { } + // register a relation between 2 ssa names at a stmt. + void register_stmt (gimple *, relation_kind, tree, tree); + // 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; + // 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. + virtual relation_kind query_relation (basic_block, tree, tree) = 0; + // Query for a relation between two equivalency stes in a basic block. + virtual relation_kind query_relation (basic_block, const_bitmap, + const_bitmap) = 0; + + virtual void dump (FILE *, basic_block) const = 0; + virtual void dump (FILE *) const = 0; + void debug () const; +}; + // Declared internally in value-relation.cc class equiv_chain; @@ -81,15 +106,18 @@ class equiv_chain; // can be represented only on edges whose destination is a single-pred block, // and the equivalence is simply applied to that succesor block. -class equiv_oracle +class equiv_oracle : public relation_oracle { public: equiv_oracle (); ~equiv_oracle (); - const_bitmap equiv_set (tree ssa, basic_block bb) const; - void register_equiv (basic_block bb, tree ssa1, tree ssa2); + const_bitmap equiv_set (tree ssa, basic_block bb); + void register_relation (basic_block bb, relation_kind k, tree ssa1, + tree ssa2); + relation_kind query_relation (basic_block, tree, tree); + relation_kind query_relation (basic_block, const_bitmap, const_bitmap); void dump (FILE *f, basic_block bb) const; void dump (FILE *f) const; @@ -99,6 +127,7 @@ protected: private: bitmap m_equiv_set; // Index by ssa-name. true if an equivalence exists. vec m_equiv; // Index by BB. list of equivalences. + vec m_self_equiv; // Index by ssa-name, self equivalency set. void limit_check (basic_block bb = NULL); equiv_chain *find_equiv_block (unsigned ssa, int bb) const; @@ -117,6 +146,7 @@ class relation_chain_head public: bitmap m_names; // ssa_names with relations in this block. class relation_chain *m_head; // List of relations in block. + relation_kind find_relation (const_bitmap b1, const_bitmap b2) const; }; // A relation oracle maintains a set of relations between ssa_names using the @@ -129,36 +159,32 @@ public: // relation to the destination block of the edge, but ONLY if that block // has a single successor. For now. -class relation_oracle : public equiv_oracle +class dom_oracle : public equiv_oracle { public: - relation_oracle (); - ~relation_oracle (); + dom_oracle (); + ~dom_oracle (); - void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2); - void register_relation (edge e, relation_kind k, tree op1, tree op2); + void register_relation (basic_block bb, relation_kind k, tree op1, tree op2); relation_kind query_relation (basic_block bb, tree ssa1, tree ssa2); + relation_kind query_relation (basic_block bb, const_bitmap b1, + const_bitmap b2); void dump (FILE *f, basic_block bb) const; void dump (FILE *f) const; - void debug () const; private: bitmap m_tmp, m_tmp2; bitmap m_relation_set; // Index by ssa-name. True if a relation exists vec m_relations; // Index by BB, list of relations. relation_kind find_relation_block (unsigned bb, const_bitmap b1, - const_bitmap b2); - relation_kind find_relation_dom (basic_block bb, const_bitmap b1, - const_bitmap b2); + const_bitmap b2) const; relation_kind find_relation_block (int bb, unsigned v1, unsigned v2, - relation_chain **obj = NULL); - relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2); - void register_relation (basic_block bb, relation_kind k, tree op1, tree op2, - bool transitive_p = false); + relation_chain **obj = NULL) const; + relation_kind find_relation_dom (basic_block bb, unsigned v1, unsigned v2) const; + relation_chain *set_one_relation (basic_block bb, relation_kind k, tree op1, + tree op2); void register_transitives (basic_block, const class value_relation &); - void register_transitives (basic_block, const value_relation &, const_bitmap, - const_bitmap); }; -- 2.17.2