blob: f2d95c4393eee23e8951ac86447746adfb8ea238 [file] [log] [blame]
/* Context-aware pointer equivalence tracker.
Copyright (C) 2020-2022 Free Software Foundation, Inc.
Contributed by Aldy Hernandez <aldyh@redhat.com>
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
<http://www.gnu.org/licenses/>. */
#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-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);
private:
auto_vec<std::pair <tree, tree>> m_stack;
auto_vec<tree> m_replacements;
const std::pair <tree, tree> m_marker = std::make_pair (NULL, NULL);
};
ssa_equiv_stack::ssa_equiv_stack ()
{
m_replacements.safe_grow_cleared (num_ssa_names + 1);
}
// 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<tree, tree> 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)
{
unsigned v = SSA_NAME_VERSION (name);
if (v >= m_replacements.length ())
m_replacements.safe_grow_cleared (num_ssa_names + 1);
tree old = m_replacements[v];
m_replacements[v] = replacement;
m_stack.safe_push (std::make_pair (name, old));
}
// Return the equivalence of NAME.
tree
ssa_equiv_stack::get_replacement (tree name)
{
unsigned v = SSA_NAME_VERSION (name);
if (v >= m_replacements.length ())
m_replacements.safe_grow_cleared (num_ssa_names + 1);
return m_replacements[v];
}
pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r)
{
m_ranger = r;
m_global_points.safe_grow_cleared (num_ssa_names + 1);
m_cond_points = new ssa_equiv_stack;
}
pointer_equiv_analyzer::~pointer_equiv_analyzer ()
{
delete m_cond_points;
}
// Set the global pointer equivalency for SSA to POINTEE.
void
pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee)
{
unsigned v = SSA_NAME_VERSION (ssa);
if (v >= m_global_points.length ())
m_global_points.safe_grow_cleared (num_ssa_names + 1);
m_global_points[v] = 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)
{
unsigned v = SSA_NAME_VERSION (ssa);
if (v >= m_global_points.length ())
m_global_points.safe_grow_cleared (num_ssa_names + 1);
tree ret = m_global_points[v];
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)
{
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));
}
}