From patchwork Mon Sep 13 11:33:02 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 44943 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 612E9385783A for ; Mon, 13 Sep 2021 11:33:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 612E9385783A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1631532838; bh=gDgQ9eLFlAK5IkkO/TVRuoXpmABDNXpt4YzoH7pZWi4=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=gOOfMLAn6RoHOApN8XU6Br9k93CMrxM73LZ+Vx/KeT514lCVHBjQiZnKhghZppwGK MGNmUJYa+2tBuhr2RFzYN4+2yWAgPP2wDSmOUXtvqXSOzjvWQAOot4p9iSKgT7lga/ 6ZaPCtKXxNZkaqcHhXopzQ2kbFd0jici4U6hM/TQ= 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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 5025E385841A for ; Mon, 13 Sep 2021 11:33:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5025E385841A Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-451-gYgbKxeAN3-_cw7MckqKXg-1; Mon, 13 Sep 2021 07:33:23 -0400 X-MC-Unique: gYgbKxeAN3-_cw7MckqKXg-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 44FED1006AA4 for ; Mon, 13 Sep 2021 11:33:22 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.193.150]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 4D47A1001281; Mon, 13 Sep 2021 11:33:21 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.16.1/8.15.2) with ESMTPS id 18DBXIVC1880427 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Mon, 13 Sep 2021 13:33:18 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.16.1/8.16.1/Submit) id 18DBXHY51880426; Mon, 13 Sep 2021 13:33:17 +0200 To: GCC patches Subject: [COMMITTED] Move pointer_equiv_analyzer to new file. Date: Mon, 13 Sep 2021 13:33:02 +0200 Message-Id: <20210913113301.1880371-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, 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: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" We need to use the pointer equivalence tracking from evrp in the jump threader. Instead of moving it to some *evrp.h header, it's cleaner for it to live in its own file, since it's completely independent and not evrp specific. Tested on x86-64 Linux. gcc/ChangeLog: * Makefile.in (OBJS): Add value-pointer-equiv.o. * gimple-ssa-evrp.c (class ssa_equiv_stack): Move to value-pointer-equiv.*. (ssa_equiv_stack::ssa_equiv_stack): Same. (ssa_equiv_stack::enter): Same. (ssa_equiv_stack::leave): Same. (ssa_equiv_stack::push_replacement): Same. (ssa_equiv_stack::get_replacement): Same. (is_pointer_ssa): Same. (class pointer_equiv_analyzer): Same. (pointer_equiv_analyzer::pointer_equiv_analyzer): Same. (pointer_equiv_analyzer::~pointer_equiv_analyzer): Same. (pointer_equiv_analyzer::set_global_equiv): Same. (pointer_equiv_analyzer::set_cond_equiv): Same. (pointer_equiv_analyzer::get_equiv): Same. (pointer_equiv_analyzer::enter): Same. (pointer_equiv_analyzer::leave): Same. (pointer_equiv_analyzer::get_equiv_expr): Same. (pta_valueize): Same. (pointer_equiv_analyzer::visit_stmt): Same. (pointer_equiv_analyzer::visit_edge): Same. (hybrid_folder::value_of_expr): Same. (hybrid_folder::value_on_edge): Same. * value-pointer-equiv.cc: New file. * value-pointer-equiv.h: New file. --- gcc/Makefile.in | 1 + gcc/gimple-ssa-evrp.c | 302 +------------------------------------ gcc/value-pointer-equiv.cc | 302 +++++++++++++++++++++++++++++++++++++ gcc/value-pointer-equiv.h | 62 ++++++++ 4 files changed, 370 insertions(+), 297 deletions(-) create mode 100644 gcc/value-pointer-equiv.cc create mode 100644 gcc/value-pointer-equiv.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index f0c560fe45b..f3877128524 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1698,6 +1698,7 @@ OBJS = \ typed-splay-tree.o \ unique-ptr-tests.o \ valtrack.o \ + value-pointer-equiv.o \ value-query.o \ value-range.o \ value-range-equiv.o \ diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c index 61de5013d6d..254542ef4cc 100644 --- a/gcc/gimple-ssa-evrp.c +++ b/gcc/gimple-ssa-evrp.c @@ -43,299 +43,7 @@ along with GCC; see the file COPYING3. If not see #include "gimple-ssa-evrp-analyze.h" #include "gimple-range.h" #include "fold-const.h" - -// Unwindable SSA equivalence table for pointers. -// -// The main query point is get_replacement() which returns what a -// given SSA can be replaced with in the current scope. - -class ssa_equiv_stack -{ -public: - ssa_equiv_stack (); - void enter (basic_block); - void leave (basic_block); - void push_replacement (tree name, tree replacement); - tree get_replacement (tree name) const; - -private: - auto_vec> m_stack; - auto_vec m_replacements; - const std::pair m_marker = std::make_pair (NULL, NULL); -}; - -ssa_equiv_stack::ssa_equiv_stack () -{ - m_replacements.safe_grow_cleared (num_ssa_names); -} - -// Pushes a marker at the given point. - -void -ssa_equiv_stack::enter (basic_block) -{ - m_stack.safe_push (m_marker); -} - -// Pops the stack to the last marker, while performing replacements -// along the way. - -void -ssa_equiv_stack::leave (basic_block) -{ - gcc_checking_assert (!m_stack.is_empty ()); - while (m_stack.last () != m_marker) - { - std::pair e = m_stack.pop (); - m_replacements[SSA_NAME_VERSION (e.first)] = e.second; - } - m_stack.pop (); -} - -// Set the equivalence of NAME to REPLACEMENT. - -void -ssa_equiv_stack::push_replacement (tree name, tree replacement) -{ - tree old = m_replacements[SSA_NAME_VERSION (name)]; - m_replacements[SSA_NAME_VERSION (name)] = replacement; - m_stack.safe_push (std::make_pair (name, old)); -} - -// Return the equivalence of NAME. - -tree -ssa_equiv_stack::get_replacement (tree name) const -{ - return m_replacements[SSA_NAME_VERSION (name)]; -} - -// Return TRUE if EXPR is an SSA holding a pointer. - -static bool inline -is_pointer_ssa (tree expr) -{ - return TREE_CODE (expr) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (expr)); -} - -// Simple context-aware pointer equivalency analyzer that returns what -// a pointer SSA name is equivalent to at a given point during a walk -// of the IL. -// -// Note that global equivalency take priority over conditional -// equivalency. That is, p = &q takes priority over a later p == &t. -// -// This class is meant to be called during a DOM walk. - -class pointer_equiv_analyzer -{ -public: - pointer_equiv_analyzer (gimple_ranger *r); - ~pointer_equiv_analyzer (); - void enter (basic_block); - void leave (basic_block); - void visit_stmt (gimple *stmt); - tree get_equiv (tree ssa) const; - -private: - void visit_edge (edge e); - tree get_equiv_expr (tree_code code, tree expr) const; - void set_global_equiv (tree ssa, tree pointee); - void set_cond_equiv (tree ssa, tree pointee); - - gimple_ranger *m_ranger; - // Global pointer equivalency indexed by SSA_NAME_VERSION. - tree *m_global_points; - // Conditional pointer equivalency. - ssa_equiv_stack m_cond_points; -}; - -pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r) -{ - m_ranger = r; - m_global_points = new tree[num_ssa_names] (); -} - -pointer_equiv_analyzer::~pointer_equiv_analyzer () -{ - delete[] m_global_points; -} - -// Set the global pointer equivalency for SSA to POINTEE. - -void -pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee) -{ - m_global_points[SSA_NAME_VERSION (ssa)] = pointee; -} - -// Set the conditional pointer equivalency for SSA to POINTEE. - -void -pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee) -{ - m_cond_points.push_replacement (ssa, pointee); -} - -// Return the current pointer equivalency info for SSA, or NULL if -// none is available. Note that global info takes priority over -// conditional info. - -tree -pointer_equiv_analyzer::get_equiv (tree ssa) const -{ - tree ret = m_global_points[SSA_NAME_VERSION (ssa)]; - if (ret) - return ret; - return m_cond_points.get_replacement (ssa); -} - -// Method to be called on entry to a BB. - -void -pointer_equiv_analyzer::enter (basic_block bb) -{ - m_cond_points.enter (bb); - - for (gphi_iterator iter = gsi_start_phis (bb); - !gsi_end_p (iter); - gsi_next (&iter)) - { - gphi *phi = iter.phi (); - tree lhs = gimple_phi_result (phi); - if (!POINTER_TYPE_P (TREE_TYPE (lhs))) - continue; - tree arg0 = gimple_phi_arg_def (phi, 0); - if (TREE_CODE (arg0) == SSA_NAME && !is_gimple_min_invariant (arg0)) - arg0 = get_equiv (arg0); - if (arg0 && is_gimple_min_invariant (arg0)) - { - // If all the PHI args point to the same place, set the - // pointer equivalency info for the PHI result. This can - // happen for passes that create redundant PHIs like - // PHI<&foo, &foo> or PHI<&foo>. - for (size_t i = 1; i < gimple_phi_num_args (phi); ++i) - { - tree argi = gimple_phi_arg_def (phi, i); - if (TREE_CODE (argi) == SSA_NAME - && !is_gimple_min_invariant (argi)) - argi = get_equiv (argi); - if (!argi || !operand_equal_p (arg0, argi)) - return; - } - set_global_equiv (lhs, arg0); - } - } - - edge pred = single_pred_edge_ignoring_loop_edges (bb, false); - if (pred) - visit_edge (pred); -} - -// Method to be called on exit from a BB. - -void -pointer_equiv_analyzer::leave (basic_block bb) -{ - m_cond_points.leave (bb); -} - -// Helper function to return the pointer equivalency information for -// EXPR from a gimple statement with CODE. This returns either the -// cached pointer equivalency info for an SSA, or an invariant in case -// EXPR is one (i.e. &foo). Returns NULL if EXPR is neither an SSA -// nor an invariant. - -tree -pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr) const -{ - if (code == SSA_NAME) - return get_equiv (expr); - - if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS - && is_gimple_min_invariant (expr)) - return expr; - - return NULL; -} - -// Hack to provide context to the gimple fold callback. -static struct -{ - gimple *m_stmt; - gimple_ranger *m_ranger; - pointer_equiv_analyzer *m_pta; -} x_fold_context; - -// Gimple fold callback. -static tree -pta_valueize (tree name) -{ - tree ret - = x_fold_context.m_ranger->value_of_expr (name, x_fold_context.m_stmt); - - if (!ret && is_pointer_ssa (name)) - ret = x_fold_context.m_pta->get_equiv (name); - - return ret ? ret : name; -} - -// Method to be called on gimple statements during traversal of the IL. - -void -pointer_equiv_analyzer::visit_stmt (gimple *stmt) -{ - if (gimple_code (stmt) != GIMPLE_ASSIGN) - return; - - tree lhs = gimple_assign_lhs (stmt); - if (!is_pointer_ssa (lhs)) - return; - - tree rhs = gimple_assign_rhs1 (stmt); - rhs = get_equiv_expr (gimple_assign_rhs_code (stmt), rhs); - if (rhs) - { - set_global_equiv (lhs, rhs); - return; - } - - // If we couldn't find anything, try fold. - x_fold_context = { stmt, m_ranger, this}; - rhs = gimple_fold_stmt_to_constant_1 (stmt, pta_valueize, pta_valueize); - if (rhs) - { - rhs = get_equiv_expr (TREE_CODE (rhs), rhs); - if (rhs) - { - set_global_equiv (lhs, rhs); - return; - } - } -} - -// If the edge in E is a conditional that sets a pointer equality, set the -// conditional pointer equivalency information. - -void -pointer_equiv_analyzer::visit_edge (edge e) -{ - gimple *stmt = last_stmt (e->src); - tree lhs; - // Recognize: x_13 [==,!=] &foo. - if (stmt - && gimple_code (stmt) == GIMPLE_COND - && (lhs = gimple_cond_lhs (stmt)) - && TREE_CODE (lhs) == SSA_NAME - && POINTER_TYPE_P (TREE_TYPE (lhs)) - && TREE_CODE (gimple_cond_rhs (stmt)) == ADDR_EXPR) - { - tree_code code = gimple_cond_code (stmt); - if ((code == EQ_EXPR && e->flags & EDGE_TRUE_VALUE) - || ((code == NE_EXPR && e->flags & EDGE_FALSE_VALUE))) - set_cond_equiv (lhs, gimple_cond_rhs (stmt)); - } -} +#include "value-pointer-equiv.h" // This is the classic EVRP folder which uses a dominator walk and pushes // ranges into the next block if it is a single predecessor block. @@ -430,7 +138,7 @@ public: tree value_of_expr (tree name, gimple *s = NULL) OVERRIDE { tree ret = m_ranger->value_of_expr (name, s); - if (!ret && is_pointer_ssa (name)) + if (!ret && supported_pointer_equiv_p (name)) ret = m_pta->get_equiv (name); return ret; } @@ -438,7 +146,7 @@ public: tree value_on_edge (edge e, tree name) OVERRIDE { tree ret = m_ranger->value_on_edge (e, name); - if (!ret && is_pointer_ssa (name)) + if (!ret && supported_pointer_equiv_p (name)) ret = m_pta->get_equiv (name); return ret; } @@ -570,7 +278,7 @@ hybrid_folder::value_of_expr (tree op, gimple *stmt) { tree evrp_ret = evrp_folder::value_of_expr (op, stmt); tree ranger_ret = m_ranger->value_of_expr (op, stmt); - if (!ranger_ret && is_pointer_ssa (op)) + if (!ranger_ret && supported_pointer_equiv_p (op)) ranger_ret = m_pta->get_equiv (op); return choose_value (evrp_ret, ranger_ret); } @@ -582,7 +290,7 @@ hybrid_folder::value_on_edge (edge e, tree op) // via hybrid_folder::value_of_expr, but without an edge. tree evrp_ret = evrp_folder::value_of_expr (op, NULL); tree ranger_ret = m_ranger->value_on_edge (e, op); - if (!ranger_ret && is_pointer_ssa (op)) + if (!ranger_ret && supported_pointer_equiv_p (op)) ranger_ret = m_pta->get_equiv (op); return choose_value (evrp_ret, ranger_ret); } diff --git a/gcc/value-pointer-equiv.cc b/gcc/value-pointer-equiv.cc new file mode 100644 index 00000000000..7d2658b77a4 --- /dev/null +++ b/gcc/value-pointer-equiv.cc @@ -0,0 +1,302 @@ +/* Context-aware pointer equivalence tracker. + Copyright (C) 2020-2021 Free Software Foundation, Inc. + Contributed by Aldy Hernandez + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "cfganal.h" +#include "gimple-fold.h" +#include "tree-eh.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "tree-ssa-loop-manip.h" +#include "tree-ssa-loop.h" +#include "cfgloop.h" +#include "tree-scalar-evolution.h" +#include "tree-ssa-propagate.h" +#include "alloc-pool.h" +#include "domwalk.h" +#include "tree-cfgcleanup.h" +#include "vr-values.h" +#include "gimple-ssa-evrp-analyze.h" +#include "gimple-range.h" +#include "fold-const.h" +#include "value-pointer-equiv.h" + +// Unwindable SSA equivalence table for pointers. +// +// The main query point is get_replacement() which returns what a +// given SSA can be replaced with in the current scope. + +class ssa_equiv_stack +{ +public: + ssa_equiv_stack (); + void enter (basic_block); + void leave (basic_block); + void push_replacement (tree name, tree replacement); + tree get_replacement (tree name) const; + +private: + auto_vec> m_stack; + auto_vec m_replacements; + const std::pair m_marker = std::make_pair (NULL, NULL); +}; + +ssa_equiv_stack::ssa_equiv_stack () +{ + m_replacements.safe_grow_cleared (num_ssa_names); +} + +// Pushes a marker at the given point. + +void +ssa_equiv_stack::enter (basic_block) +{ + m_stack.safe_push (m_marker); +} + +// Pops the stack to the last marker, while performing replacements +// along the way. + +void +ssa_equiv_stack::leave (basic_block) +{ + gcc_checking_assert (!m_stack.is_empty ()); + while (m_stack.last () != m_marker) + { + std::pair e = m_stack.pop (); + m_replacements[SSA_NAME_VERSION (e.first)] = e.second; + } + m_stack.pop (); +} + +// Set the equivalence of NAME to REPLACEMENT. + +void +ssa_equiv_stack::push_replacement (tree name, tree replacement) +{ + tree old = m_replacements[SSA_NAME_VERSION (name)]; + m_replacements[SSA_NAME_VERSION (name)] = replacement; + m_stack.safe_push (std::make_pair (name, old)); +} + +// Return the equivalence of NAME. + +tree +ssa_equiv_stack::get_replacement (tree name) const +{ + return m_replacements[SSA_NAME_VERSION (name)]; +} + +pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r) +{ + m_ranger = r; + m_global_points = new tree[num_ssa_names] (); + m_cond_points = new ssa_equiv_stack; +} + +pointer_equiv_analyzer::~pointer_equiv_analyzer () +{ + delete[] m_global_points; + delete m_cond_points; +} + +// Set the global pointer equivalency for SSA to POINTEE. + +void +pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee) +{ + m_global_points[SSA_NAME_VERSION (ssa)] = pointee; +} + +// Set the conditional pointer equivalency for SSA to POINTEE. + +void +pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee) +{ + m_cond_points->push_replacement (ssa, pointee); +} + +// Return the current pointer equivalency info for SSA, or NULL if +// none is available. Note that global info takes priority over +// conditional info. + +tree +pointer_equiv_analyzer::get_equiv (tree ssa) const +{ + tree ret = m_global_points[SSA_NAME_VERSION (ssa)]; + if (ret) + return ret; + return m_cond_points->get_replacement (ssa); +} + +// Method to be called on entry to a BB. + +void +pointer_equiv_analyzer::enter (basic_block bb) +{ + m_cond_points->enter (bb); + + for (gphi_iterator iter = gsi_start_phis (bb); + !gsi_end_p (iter); + gsi_next (&iter)) + { + gphi *phi = iter.phi (); + tree lhs = gimple_phi_result (phi); + if (!POINTER_TYPE_P (TREE_TYPE (lhs))) + continue; + tree arg0 = gimple_phi_arg_def (phi, 0); + if (TREE_CODE (arg0) == SSA_NAME && !is_gimple_min_invariant (arg0)) + arg0 = get_equiv (arg0); + if (arg0 && is_gimple_min_invariant (arg0)) + { + // If all the PHI args point to the same place, set the + // pointer equivalency info for the PHI result. This can + // happen for passes that create redundant PHIs like + // PHI<&foo, &foo> or PHI<&foo>. + for (size_t i = 1; i < gimple_phi_num_args (phi); ++i) + { + tree argi = gimple_phi_arg_def (phi, i); + if (TREE_CODE (argi) == SSA_NAME + && !is_gimple_min_invariant (argi)) + argi = get_equiv (argi); + if (!argi || !operand_equal_p (arg0, argi)) + return; + } + set_global_equiv (lhs, arg0); + } + } + + edge pred = single_pred_edge_ignoring_loop_edges (bb, false); + if (pred) + visit_edge (pred); +} + +// Method to be called on exit from a BB. + +void +pointer_equiv_analyzer::leave (basic_block bb) +{ + m_cond_points->leave (bb); +} + +// Helper function to return the pointer equivalency information for +// EXPR from a gimple statement with CODE. This returns either the +// cached pointer equivalency info for an SSA, or an invariant in case +// EXPR is one (i.e. &foo). Returns NULL if EXPR is neither an SSA +// nor an invariant. + +tree +pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr) const +{ + if (code == SSA_NAME) + return get_equiv (expr); + + if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS + && is_gimple_min_invariant (expr)) + return expr; + + return NULL; +} + +// Hack to provide context to the gimple fold callback. +static struct +{ + gimple *m_stmt; + gimple_ranger *m_ranger; + pointer_equiv_analyzer *m_pta; +} x_fold_context; + +// Gimple fold callback. +static tree +pta_valueize (tree name) +{ + tree ret + = x_fold_context.m_ranger->value_of_expr (name, x_fold_context.m_stmt); + + if (!ret && supported_pointer_equiv_p (name)) + ret = x_fold_context.m_pta->get_equiv (name); + + return ret ? ret : name; +} + +// Method to be called on gimple statements during traversal of the IL. + +void +pointer_equiv_analyzer::visit_stmt (gimple *stmt) +{ + if (gimple_code (stmt) != GIMPLE_ASSIGN) + return; + + tree lhs = gimple_assign_lhs (stmt); + if (!supported_pointer_equiv_p (lhs)) + return; + + tree rhs = gimple_assign_rhs1 (stmt); + rhs = get_equiv_expr (gimple_assign_rhs_code (stmt), rhs); + if (rhs) + { + set_global_equiv (lhs, rhs); + return; + } + + // If we couldn't find anything, try fold. + x_fold_context = { stmt, m_ranger, this}; + rhs = gimple_fold_stmt_to_constant_1 (stmt, pta_valueize, pta_valueize); + if (rhs) + { + rhs = get_equiv_expr (TREE_CODE (rhs), rhs); + if (rhs) + { + set_global_equiv (lhs, rhs); + return; + } + } +} + +// If the edge in E is a conditional that sets a pointer equality, set the +// conditional pointer equivalency information. + +void +pointer_equiv_analyzer::visit_edge (edge e) +{ + gimple *stmt = last_stmt (e->src); + tree lhs; + // Recognize: x_13 [==,!=] &foo. + if (stmt + && gimple_code (stmt) == GIMPLE_COND + && (lhs = gimple_cond_lhs (stmt)) + && TREE_CODE (lhs) == SSA_NAME + && POINTER_TYPE_P (TREE_TYPE (lhs)) + && TREE_CODE (gimple_cond_rhs (stmt)) == ADDR_EXPR) + { + tree_code code = gimple_cond_code (stmt); + if ((code == EQ_EXPR && e->flags & EDGE_TRUE_VALUE) + || ((code == NE_EXPR && e->flags & EDGE_FALSE_VALUE))) + set_cond_equiv (lhs, gimple_cond_rhs (stmt)); + } +} diff --git a/gcc/value-pointer-equiv.h b/gcc/value-pointer-equiv.h new file mode 100644 index 00000000000..0921579d52a --- /dev/null +++ b/gcc/value-pointer-equiv.h @@ -0,0 +1,62 @@ +/* Header file for the context-aware pointer equivalence tracker. + Copyright (C) 2020-2021 Free Software Foundation, Inc. + Contributed by Aldy Hernandez + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_VALUE_POINTER_EQUIV_H +#define GCC_VALUE_POINTER_EQUIV_H + +// Simple context-aware pointer equivalency analyzer that returns what +// a pointer SSA name is equivalent to at a given point during a walk +// of the IL. +// +// Note that global equivalency take priority over conditional +// equivalency. That is, p = &q takes priority over a later p == &t. +// +// This class is meant to be called during a DOM walk. + +class pointer_equiv_analyzer +{ +public: + pointer_equiv_analyzer (gimple_ranger *r); + ~pointer_equiv_analyzer (); + void enter (basic_block); + void leave (basic_block); + void visit_stmt (gimple *stmt); + tree get_equiv (tree ssa) const; + +private: + void visit_edge (edge e); + tree get_equiv_expr (tree_code code, tree expr) const; + void set_global_equiv (tree ssa, tree pointee); + void set_cond_equiv (tree ssa, tree pointee); + + gimple_ranger *m_ranger; + // Global pointer equivalency indexed by SSA_NAME_VERSION. + tree *m_global_points; + // Conditional pointer equivalency. + class ssa_equiv_stack *m_cond_points; +}; + +inline bool +supported_pointer_equiv_p (tree expr) +{ + return TREE_CODE (expr) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (expr)); +} + +#endif // GCC_VALUE_POINTER_EQUIV_H