/* SSA Dominator optimizations for trees
- Copyright (C) 2001-2019 Free Software Foundation, Inc.
+ Copyright (C) 2001-2021 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
#include "domwalk.h"
#include "tree-ssa-propagate.h"
#include "tree-ssa-threadupdate.h"
-#include "params.h"
#include "tree-ssa-scopedtables.h"
#include "tree-ssa-threadedge.h"
#include "tree-ssa-dom.h"
#include "tree-vrp.h"
#include "vr-values.h"
#include "gimple-ssa-evrp-analyze.h"
+#include "alias.h"
/* This file implements optimizations on the dominator tree. */
void
free_dom_edge_info (edge e)
{
- class edge_info *edge_info = (struct edge_info *)e->aux;
+ class edge_info *edge_info = (class edge_info *)e->aux;
if (edge_info)
delete edge_info;
bool can_infer_simple_equiv
= !(HONOR_SIGNED_ZEROS (op0)
&& real_zerop (op0));
- struct edge_info *edge_info;
+ class edge_info *edge_info;
edge_info = new class edge_info (true_edge);
record_conditions (&edge_info->cond_equivalences, cond, inverted);
bool can_infer_simple_equiv
= !(HONOR_SIGNED_ZEROS (op1)
&& (TREE_CODE (op1) == SSA_NAME || real_zerop (op1)));
- struct edge_info *edge_info;
+ class edge_info *edge_info;
edge_info = new class edge_info (true_edge);
record_conditions (&edge_info->cond_equivalences, cond, inverted);
}
}
+class dom_jump_threader_simplifier : public jump_threader_simplifier
+{
+public:
+ dom_jump_threader_simplifier (vr_values *v,
+ avail_exprs_stack *avails)
+ : jump_threader_simplifier (v), m_avail_exprs_stack (avails) { }
+
+private:
+ tree simplify (gimple *, gimple *, basic_block, jt_state *) override;
+ avail_exprs_stack *m_avail_exprs_stack;
+};
+
+tree
+dom_jump_threader_simplifier::simplify (gimple *stmt,
+ gimple *within_stmt,
+ basic_block bb,
+ jt_state *state)
+{
+ /* First see if the conditional is in the hash table. */
+ tree cached_lhs = m_avail_exprs_stack->lookup_avail_expr (stmt,
+ false, true);
+ if (cached_lhs)
+ return cached_lhs;
+
+ return jump_threader_simplifier::simplify (stmt, within_stmt, bb, state);
+}
class dom_opt_dom_walker : public dom_walker
{
public:
dom_opt_dom_walker (cdi_direction direction,
- class const_and_copies *const_and_copies,
- class avail_exprs_stack *avail_exprs_stack,
- gcond *dummy_cond)
- : dom_walker (direction, REACHABLE_BLOCKS),
- m_const_and_copies (const_and_copies),
- m_avail_exprs_stack (avail_exprs_stack),
- evrp_range_analyzer (true),
- m_dummy_cond (dummy_cond) { }
+ jump_threader *threader,
+ jt_state *state,
+ evrp_range_analyzer *analyzer,
+ const_and_copies *const_and_copies,
+ avail_exprs_stack *avail_exprs_stack)
+ : dom_walker (direction, REACHABLE_BLOCKS)
+ {
+ m_evrp_range_analyzer = analyzer;
+ m_state = state;
+ m_dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
+ integer_zero_node, NULL, NULL);
+ m_const_and_copies = const_and_copies;
+ m_avail_exprs_stack = avail_exprs_stack;
+ m_threader = threader;
+ }
virtual edge before_dom_children (basic_block);
virtual void after_dom_children (basic_block);
class const_and_copies *m_const_and_copies;
class avail_exprs_stack *m_avail_exprs_stack;
- /* VRP data. */
- class evrp_range_analyzer evrp_range_analyzer;
-
/* Dummy condition to avoid creating lots of throw away statements. */
gcond *m_dummy_cond;
the statement is a conditional with a statically determined
value. */
edge optimize_stmt (basic_block, gimple_stmt_iterator *, bool *);
+
+
+ void test_for_singularity (gimple *, avail_exprs_stack *);
+
+ jump_threader *m_threader;
+ evrp_range_analyzer *m_evrp_range_analyzer;
+ jt_state *m_state;
};
/* Jump threading, redundancy elimination and const/copy propagation.
gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
missing. We should improve jump threading in future then
LOOPS_HAVE_PREHEADERS won't be needed here. */
- loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
-
- /* Initialize the value-handle array. */
- threadedge_initialize_values ();
+ loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES
+ | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
/* We need accurate information regarding back edges in the CFG
for jump threading; this may include back edges that are not part of
FOR_EACH_BB_FN (bb, fun)
record_edge_info (bb);
- gcond *dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
- integer_zero_node, NULL, NULL);
-
/* Recursively walk the dominator tree optimizing statements. */
- dom_opt_dom_walker walker (CDI_DOMINATORS, const_and_copies,
- avail_exprs_stack, dummy_cond);
+ evrp_range_analyzer analyzer (true);
+ dom_jump_threader_simplifier simplifier (&analyzer, avail_exprs_stack);
+ jt_state state (const_and_copies, avail_exprs_stack, &analyzer);
+ jump_threader threader (&simplifier, &state);
+ dom_opt_dom_walker walker (CDI_DOMINATORS,
+ &threader,
+ &state,
+ &analyzer,
+ const_and_copies,
+ avail_exprs_stack);
walker.walk (fun->cfg->x_entry_block_ptr);
/* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
containing any edge leaving BB. */
if (found)
FOR_EACH_EDGE (e, ei, bb->succs)
- remove_jump_threads_including (e);
+ threader.remove_jump_threads_including (e);
}
}
free_all_edge_infos ();
/* Thread jumps, creating duplicate blocks as needed. */
- cfg_altered |= thread_through_all_blocks (may_peel_loop_headers_p);
+ cfg_altered |= threader.thread_through_all_blocks (may_peel_loop_headers_p);
if (cfg_altered)
free_dominance_info (CDI_DOMINATORS);
delete avail_exprs_stack;
delete const_and_copies;
- /* Free the value-handle array. */
- threadedge_finalize_values ();
-
return 0;
}
return new pass_dominator (ctxt);
}
-/* A hack until we remove threading from tree-vrp.c and bring the
- simplification routine into the dom_opt_dom_walker class. */
-static class vr_values *x_vr_values;
-
-/* A trivial wrapper so that we can present the generic jump
- threading code with a simple API for simplifying statements. */
-static tree
-simplify_stmt_for_jump_threading (gimple *stmt,
- gimple *within_stmt ATTRIBUTE_UNUSED,
- class avail_exprs_stack *avail_exprs_stack,
- basic_block bb ATTRIBUTE_UNUSED)
-{
- /* First query our hash table to see if the the expression is available
- there. A non-NULL return value will be either a constant or another
- SSA_NAME. */
- tree cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, false, true);
- if (cached_lhs)
- return cached_lhs;
-
- /* If the hash table query failed, query VRP information. This is
- essentially the same as tree-vrp's simplification routine. The
- copy in tree-vrp is scheduled for removal in gcc-9. */
- if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
- {
- cached_lhs
- = x_vr_values->vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
- gimple_cond_lhs (cond_stmt),
- gimple_cond_rhs (cond_stmt),
- within_stmt);
- return cached_lhs;
- }
-
- if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
- {
- tree op = gimple_switch_index (switch_stmt);
- if (TREE_CODE (op) != SSA_NAME)
- return NULL_TREE;
-
- value_range *vr = x_vr_values->get_value_range (op);
- if (vr->undefined_p ()
- || vr->varying_p ()
- || vr->symbolic_p ())
- return NULL_TREE;
-
- if (vr->kind () == VR_RANGE)
- {
- size_t i, j;
-
- find_case_label_range (switch_stmt, vr->min (), vr->max (), &i, &j);
-
- if (i == j)
- {
- tree label = gimple_switch_label (switch_stmt, i);
- tree singleton;
-
- if (CASE_HIGH (label) != NULL_TREE
- ? (tree_int_cst_compare (CASE_LOW (label), vr->min ()) <= 0
- && tree_int_cst_compare (CASE_HIGH (label), vr->max ()) >= 0)
- : (vr->singleton_p (&singleton)
- && tree_int_cst_equal (CASE_LOW (label), singleton)))
- return label;
-
- if (i > j)
- return gimple_switch_label (switch_stmt, 0);
- }
- }
-
- if (vr->kind () == VR_ANTI_RANGE)
- {
- unsigned n = gimple_switch_num_labels (switch_stmt);
- tree min_label = gimple_switch_label (switch_stmt, 1);
- tree max_label = gimple_switch_label (switch_stmt, n - 1);
-
- /* The default label will be taken only if the anti-range of the
- operand is entirely outside the bounds of all the (non-default)
- case labels. */
- if (tree_int_cst_compare (vr->min (), CASE_LOW (min_label)) <= 0
- && (CASE_HIGH (max_label) != NULL_TREE
- ? tree_int_cst_compare (vr->max (), CASE_HIGH (max_label)) >= 0
- : tree_int_cst_compare (vr->max (), CASE_LOW (max_label)) >= 0))
- return gimple_switch_label (switch_stmt, 0);
- }
- return NULL_TREE;
- }
-
- if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
- {
- tree lhs = gimple_assign_lhs (assign_stmt);
- if (TREE_CODE (lhs) == SSA_NAME
- && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
- || POINTER_TYPE_P (TREE_TYPE (lhs)))
- && stmt_interesting_for_vrp (stmt))
- {
- edge dummy_e;
- tree dummy_tree;
- value_range new_vr;
- x_vr_values->extract_range_from_stmt (stmt, &dummy_e,
- &dummy_tree, &new_vr);
- tree singleton;
- if (new_vr.singleton_p (&singleton))
- return singleton;
- }
- }
- return NULL;
-}
-
/* Valueize hook for gimple_fold_stmt_to_constant_1. */
static tree
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
- evrp_range_analyzer.enter (bb);
+ m_evrp_range_analyzer->enter (bb);
/* Push a marker on the stacks of local information so that we know how
far to unwind when we finalize this block. */
continue;
}
- /* Compute range information and optimize the stmt. */
- evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
+ m_state->record_ranges_from_stmt (gsi_stmt (gsi), false);
bool removed_p = false;
taken_edge = this->optimize_stmt (bb, &gsi, &removed_p);
if (!removed_p)
void
dom_opt_dom_walker::after_dom_children (basic_block bb)
{
- x_vr_values = evrp_range_analyzer.get_vr_values ();
- thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
- m_avail_exprs_stack,
- &evrp_range_analyzer,
- simplify_stmt_for_jump_threading);
- x_vr_values = NULL;
-
- /* These remove expressions local to BB from the tables. */
+ m_threader->thread_outgoing_edges (bb);
m_avail_exprs_stack->pop_to_marker ();
m_const_and_copies->pop_to_marker ();
- evrp_range_analyzer.leave (bb);
+ m_evrp_range_analyzer->leave (bb);
}
/* Search for redundant computations in STMT. If any are found, then
tree op0 = gimple_assign_rhs1 (stmt);
tree op1 = gimple_assign_rhs2 (stmt);
tree new_rhs
- = build_fold_addr_expr (fold_build2 (MEM_REF,
- TREE_TYPE (TREE_TYPE (op0)),
- unshare_expr (op0),
- fold_convert (ptr_type_node,
- op1)));
+ = build1 (ADDR_EXPR, TREE_TYPE (op0),
+ fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (op0)),
+ unshare_expr (op0), fold_convert (ptr_type_node,
+ op1)));
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "==== ASGN ");
This is similar to code in VRP. */
-static void
-test_for_singularity (gimple *stmt, gcond *dummy_cond,
- avail_exprs_stack *avail_exprs_stack)
+void
+dom_opt_dom_walker::test_for_singularity (gimple *stmt,
+ avail_exprs_stack *avail_exprs_stack)
{
/* We want to support gimple conditionals as well as assignments
where the RHS contains a conditional. */
test_code = GE_EXPR;
/* Update the dummy statement so we can query the hash tables. */
- gimple_cond_set_code (dummy_cond, test_code);
- gimple_cond_set_lhs (dummy_cond, lhs);
- gimple_cond_set_rhs (dummy_cond, rhs);
+ gimple_cond_set_code (m_dummy_cond, test_code);
+ gimple_cond_set_lhs (m_dummy_cond, lhs);
+ gimple_cond_set_rhs (m_dummy_cond, rhs);
tree cached_lhs
- = avail_exprs_stack->lookup_avail_expr (dummy_cond, false, false);
+ = avail_exprs_stack->lookup_avail_expr (m_dummy_cond,
+ false, false);
/* If the lookup returned 1 (true), then the expression we
queried was in the hash table. As a result there is only
}
}
+/* If STMT is a comparison of two uniform vectors reduce it to a comparison
+ of scalar objects, otherwise leave STMT unchanged. */
+
+static void
+reduce_vector_comparison_to_scalar_comparison (gimple *stmt)
+{
+ if (gimple_code (stmt) == GIMPLE_COND)
+ {
+ tree lhs = gimple_cond_lhs (stmt);
+ tree rhs = gimple_cond_rhs (stmt);
+
+ /* We may have a vector comparison where both arms are uniform
+ vectors. If so, we can simplify the vector comparison down
+ to a scalar comparison. */
+ if (TREE_CODE (TREE_TYPE (lhs)) == VECTOR_TYPE
+ && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE)
+ {
+ /* If either operand is an SSA_NAME, then look back to its
+ defining statement to try and get at a suitable source. */
+ if (TREE_CODE (rhs) == SSA_NAME)
+ {
+ gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
+ if (gimple_assign_single_p (def_stmt))
+ rhs = gimple_assign_rhs1 (def_stmt);
+ }
+
+ if (TREE_CODE (lhs) == SSA_NAME)
+ {
+ gimple *def_stmt = SSA_NAME_DEF_STMT (lhs);
+ if (gimple_assign_single_p (def_stmt))
+ lhs = gimple_assign_rhs1 (def_stmt);
+ }
+
+ /* Now see if they are both uniform vectors and if so replace
+ the vector comparison with a scalar comparison. */
+ tree rhs_elem = rhs ? uniform_vector_p (rhs) : NULL_TREE;
+ tree lhs_elem = lhs ? uniform_vector_p (lhs) : NULL_TREE;
+ if (rhs_elem && lhs_elem)
+ {
+ if (dump_file && dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "Reducing vector comparison: ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ }
+
+ gimple_cond_set_rhs (as_a <gcond *>(stmt), rhs_elem);
+ gimple_cond_set_lhs (as_a <gcond *>(stmt), lhs_elem);
+ gimple_set_modified (stmt, true);
+
+ if (dump_file && dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "To scalar equivalent: ");
+ print_gimple_stmt (dump_file, stmt, 0);
+ fprintf (dump_file, "\n");
+ }
+ }
+ }
+ }
+}
+
/* Optimize the statement in block BB pointed to by iterator SI.
We try to perform some simplistic global redundancy elimination and
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
+ /* STMT may be a comparison of uniform vectors that we can simplify
+ down to a comparison of scalars. Do that transformation first
+ so that all the scalar optimizations from here onward apply. */
+ reduce_vector_comparison_to_scalar_comparison (stmt);
+
update_stmt_if_modified (stmt);
opt_stats.num_stmts++;
/* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
- cprop_into_stmt (stmt, evrp_range_analyzer.get_vr_values ());
+ cprop_into_stmt (stmt, m_evrp_range_analyzer);
/* If the statement has been modified with constant replacements,
fold its RHS before checking for redundant computations. */
SSA_NAMES. */
update_stmt_if_modified (stmt);
edge taken_edge = NULL;
- evrp_range_analyzer.vrp_visit_cond_stmt (as_a <gcond *> (stmt),
- &taken_edge);
+ m_evrp_range_analyzer->vrp_visit_cond_stmt
+ (as_a <gcond *> (stmt), &taken_edge);
if (taken_edge)
{
if (taken_edge->flags & EDGE_TRUE_VALUE)
else
new_stmt = gimple_build_assign (rhs, lhs);
gimple_set_vuse (new_stmt, gimple_vuse (stmt));
+ expr_hash_elt *elt = NULL;
cached_lhs = m_avail_exprs_stack->lookup_avail_expr (new_stmt, false,
- false);
- if (cached_lhs && operand_equal_p (rhs, cached_lhs, 0))
+ false, &elt);
+ if (cached_lhs
+ && operand_equal_p (rhs, cached_lhs, 0)
+ && refs_same_for_tbaa_p (elt->expr ()->kind == EXPR_SINGLE
+ ? elt->expr ()->ops.single.rhs
+ : NULL_TREE, lhs))
{
basic_block bb = gimple_bb (stmt);
unlink_stmt_vdef (stmt);
/* If this statement was not redundant, we may still be able to simplify
it, which may in turn allow other part of DOM or other passes to do
a better job. */
- test_for_singularity (stmt, m_dummy_cond, m_avail_exprs_stack);
+ test_for_singularity (stmt, m_avail_exprs_stack);
}
/* Record any additional equivalences created by this statement. */