/* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
- Copyright (C) 2001-2017 Free Software Foundation, Inc.
+ Copyright (C) 2001-2018 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
<stevenb@suse.de>
#include "gimplify.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
-#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "tree-dfa.h"
#include "tree-ssa.h"
#include "dbgcnt.h"
#include "domwalk.h"
#include "tree-ssa-propagate.h"
-#include "ipa-utils.h"
+#include "tree-ssa-dce.h"
#include "tree-cfgcleanup.h"
-#include "langhooks.h"
#include "alias.h"
/* Even though this file is called tree-ssa-pre.c, we actually
return expressions[id];
}
-/* Free the expression id field in all of our expressions,
- and then destroy the expressions array. */
-
-static void
-clear_expression_ids (void)
-{
- expressions.release ();
-}
-
static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes");
/* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
optimization PRE was able to perform. */
static struct
{
- /* The number of RHS computations eliminated by PRE. */
- int eliminations;
-
/* The number of new expressions/temporaries generated by PRE. */
int insertions;
static object_allocator<bitmap_set> bitmap_set_pool ("Bitmap sets");
static bitmap_obstack grand_bitmap_obstack;
-/* Set of blocks with statements that have had their EH properties changed. */
-static bitmap need_eh_cleanup;
-
-/* Set of blocks with statements that have had their AB properties changed. */
-static bitmap need_ab_cleanup;
-
/* A three tuple {e, pred, v} used to cache phi translations in the
phi_translate_table. */
gcc_unreachable ();
}
-/* Get a representative SSA_NAME for a given expression.
+/* Get a representative SSA_NAME for a given expression that is available in B.
Since all of our sub-expressions are treated as values, we require
them to be SSA_NAME's for simplicity.
Prior versions of GVNPRE used to use "value handles" here, so that
them to be usable without finding leaders). */
static tree
-get_representative_for (const pre_expr e)
+get_representative_for (const pre_expr e, basic_block b = NULL)
{
- tree name;
+ tree name, valnum = NULL_TREE;
unsigned int value_id = get_expr_value_id (e);
switch (e->kind)
{
pre_expr rep = expression_for_id (i);
if (rep->kind == NAME)
- return VN_INFO (PRE_EXPR_NAME (rep))->valnum;
+ {
+ tree name = PRE_EXPR_NAME (rep);
+ valnum = VN_INFO (name)->valnum;
+ gimple *def = SSA_NAME_DEF_STMT (name);
+ /* We have to return either a new representative or one
+ that can be used for expression simplification and thus
+ is available in B. */
+ if (! b
+ || gimple_nop_p (def)
+ || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def)))
+ return name;
+ }
else if (rep->kind == CONSTANT)
return PRE_EXPR_CONSTANT (rep);
}
to compute it. */
name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
VN_INFO_GET (name)->value_id = value_id;
- VN_INFO (name)->valnum = name;
+ VN_INFO (name)->valnum = valnum ? valnum : name;
/* ??? For now mark this SSA name for release by SCCVN. */
VN_INFO (name)->needs_insertion = true;
add_to_value (value_id, get_or_alloc_expr_for_name (name));
}
-
static pre_expr
phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
basic_block pred, basic_block phiblock);
leader = find_leader_in_sets (op_val_id, set1, set2);
result = phi_translate (leader, set1, set2, pred, phiblock);
if (result && result != leader)
- newnary->op[i] = get_representative_for (result);
+ /* Force a leader as well as we are simplifying this
+ expression. */
+ newnary->op[i] = get_representative_for (result, pred);
else if (!result)
return NULL;
return constant;
}
+ /* vn_nary_* do not valueize operands. */
+ for (i = 0; i < newnary->length; ++i)
+ if (TREE_CODE (newnary->op[i]) == SSA_NAME)
+ newnary->op[i] = VN_INFO (newnary->op[i])->valnum;
tree result = vn_nary_op_lookup_pieces (newnary->length,
newnary->opcode,
newnary->type,
PRE_EXPR_NARY (expr) = nary;
new_val_id = nary->value_id;
get_or_alloc_expression_id (expr);
- /* When we end up re-using a value number make sure that
- doesn't have unrelated (which we can't check here)
- range or points-to info on it. */
- if (result
- && INTEGRAL_TYPE_P (TREE_TYPE (result))
- && SSA_NAME_RANGE_INFO (result)
- && ! SSA_NAME_IS_DEFAULT_DEF (result))
- {
- if (! VN_INFO (result)->info.range_info)
- {
- VN_INFO (result)->info.range_info
- = SSA_NAME_RANGE_INFO (result);
- VN_INFO (result)->range_info_anti_range_p
- = SSA_NAME_ANTI_RANGE_P (result);
- }
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "clearing range info of ");
- print_generic_expr (dump_file, result);
- fprintf (dump_file, "\n");
- }
- SSA_NAME_RANGE_INFO (result) = NULL;
- }
- else if (result
- && POINTER_TYPE_P (TREE_TYPE (result))
- && SSA_NAME_PTR_INFO (result)
- && ! SSA_NAME_IS_DEFAULT_DEF (result))
- {
- if (! VN_INFO (result)->info.ptr_info)
- VN_INFO (result)->info.ptr_info
- = SSA_NAME_PTR_INFO (result);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "clearing points-to info of ");
- print_generic_expr (dump_file, result);
- fprintf (dump_file, "\n");
- }
- SSA_NAME_PTR_INFO (result) = NULL;
- }
}
else
{
if (changed || newvuse != vuse)
{
unsigned int new_val_id;
- pre_expr constant;
tree result = vn_reference_lookup_pieces (newvuse, ref->set,
ref->type,
expr->id = 0;
if (newref)
- {
- PRE_EXPR_REFERENCE (expr) = newref;
- constant = fully_constant_expression (expr);
- if (constant != expr)
- return constant;
-
- new_val_id = newref->value_id;
- get_or_alloc_expression_id (expr);
- }
+ new_val_id = newref->value_id;
else
{
if (changed || !same_valid)
newoperands,
result, new_val_id);
newoperands = vNULL;
- PRE_EXPR_REFERENCE (expr) = newref;
- constant = fully_constant_expression (expr);
- if (constant != expr)
- return constant;
- get_or_alloc_expression_id (expr);
}
+ PRE_EXPR_REFERENCE (expr) = newref;
+ get_or_alloc_expression_id (expr);
add_to_value (new_val_id, expr);
}
newoperands.release ();
ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
-*/
+
+ Note that clean() is deferred until after the iteration. */
static bool
compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
bitmap_value_insert_into_set (ANTIC_IN (block),
expression_for_id (bii));
- clean (ANTIC_IN (block));
+ /* clean (ANTIC_IN (block)) is defered to after the iteration converged
+ because it can cause non-convergence, see for example PR81181. */
if (!bitmap_set_equal (old, ANTIC_IN (block)))
changed = true;
gcc_checking_assert (num_iterations < 500);
}
+ /* We have to clean after the dataflow problem converged as cleaning
+ can cause non-convergence because it is based on expressions
+ rather than values. */
+ FOR_EACH_BB_FN (block, cfun)
+ clean (ANTIC_IN (block));
+
statistics_histogram_event (cfun, "compute_antic iterations",
num_iterations);
if (TREE_CODE (baseop) == ADDR_EXPR
&& handled_component_p (TREE_OPERAND (baseop, 0)))
{
- HOST_WIDE_INT off;
+ poly_int64 off;
tree base;
base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
&off);
that value numbering saw through. */
case NAME:
folded = PRE_EXPR_NAME (expr);
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded))
+ return NULL_TREE;
if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
return folded;
break;
gcc_assert (!(pred->flags & EDGE_ABNORMAL));
if (!gimple_seq_empty_p (stmts))
{
- gsi_insert_seq_on_edge (pred, stmts);
+ basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts);
+ gcc_assert (! new_bb);
insertions = true;
}
if (!builtexpr)
}
-/* Local state for the eliminate domwalk. */
-static vec<gimple *> el_to_remove;
-static vec<gimple *> el_to_fixup;
-static unsigned int el_todo;
-static vec<tree> el_avail;
-static vec<tree> el_avail_stack;
-
-/* Return a leader for OP that is available at the current point of the
- eliminate domwalk. */
-
-static tree
-eliminate_avail (tree op)
-{
- tree valnum = VN_INFO (op)->valnum;
- if (TREE_CODE (valnum) == SSA_NAME)
- {
- if (SSA_NAME_IS_DEFAULT_DEF (valnum))
- return valnum;
- if (el_avail.length () > SSA_NAME_VERSION (valnum))
- return el_avail[SSA_NAME_VERSION (valnum)];
- }
- else if (is_gimple_min_invariant (valnum))
- return valnum;
- return NULL_TREE;
-}
-
-/* At the current point of the eliminate domwalk make OP available. */
-
-static void
-eliminate_push_avail (tree op)
-{
- tree valnum = VN_INFO (op)->valnum;
- if (TREE_CODE (valnum) == SSA_NAME)
- {
- if (el_avail.length () <= SSA_NAME_VERSION (valnum))
- el_avail.safe_grow_cleared (SSA_NAME_VERSION (valnum) + 1);
- tree pushop = op;
- if (el_avail[SSA_NAME_VERSION (valnum)])
- pushop = el_avail[SSA_NAME_VERSION (valnum)];
- el_avail_stack.safe_push (pushop);
- el_avail[SSA_NAME_VERSION (valnum)] = op;
- }
-}
-
-/* Insert the expression recorded by SCCVN for VAL at *GSI. Returns
- the leader for the expression if insertion was successful. */
-
-static tree
-eliminate_insert (gimple_stmt_iterator *gsi, tree val)
-{
- /* We can insert a sequence with a single assignment only. */
- gimple_seq stmts = VN_INFO (val)->expr;
- if (!gimple_seq_singleton_p (stmts))
- return NULL_TREE;
- gassign *stmt = dyn_cast <gassign *> (gimple_seq_first_stmt (stmts));
- if (!stmt
- || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
- && gimple_assign_rhs_code (stmt) != VIEW_CONVERT_EXPR
- && gimple_assign_rhs_code (stmt) != BIT_FIELD_REF
- && (gimple_assign_rhs_code (stmt) != BIT_AND_EXPR
- || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)))
- return NULL_TREE;
-
- tree op = gimple_assign_rhs1 (stmt);
- if (gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
- || gimple_assign_rhs_code (stmt) == BIT_FIELD_REF)
- op = TREE_OPERAND (op, 0);
- tree leader = TREE_CODE (op) == SSA_NAME ? eliminate_avail (op) : op;
- if (!leader)
- return NULL_TREE;
-
- tree res;
- stmts = NULL;
- if (gimple_assign_rhs_code (stmt) == BIT_FIELD_REF)
- res = gimple_build (&stmts, BIT_FIELD_REF,
- TREE_TYPE (val), leader,
- TREE_OPERAND (gimple_assign_rhs1 (stmt), 1),
- TREE_OPERAND (gimple_assign_rhs1 (stmt), 2));
- else if (gimple_assign_rhs_code (stmt) == BIT_AND_EXPR)
- res = gimple_build (&stmts, BIT_AND_EXPR,
- TREE_TYPE (val), leader, gimple_assign_rhs2 (stmt));
- else
- res = gimple_build (&stmts, gimple_assign_rhs_code (stmt),
- TREE_TYPE (val), leader);
- if (TREE_CODE (res) != SSA_NAME
- || SSA_NAME_IS_DEFAULT_DEF (res)
- || gimple_bb (SSA_NAME_DEF_STMT (res)))
- {
- gimple_seq_discard (stmts);
-
- /* During propagation we have to treat SSA info conservatively
- and thus we can end up simplifying the inserted expression
- at elimination time to sth not defined in stmts. */
- /* But then this is a redundancy we failed to detect. Which means
- res now has two values. That doesn't play well with how
- we track availability here, so give up. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- if (TREE_CODE (res) == SSA_NAME)
- res = eliminate_avail (res);
- if (res)
- {
- fprintf (dump_file, "Failed to insert expression for value ");
- print_generic_expr (dump_file, val);
- fprintf (dump_file, " which is really fully redundant to ");
- print_generic_expr (dump_file, res);
- fprintf (dump_file, "\n");
- }
- }
-
- return NULL_TREE;
- }
- else
- {
- gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
- VN_INFO_GET (res)->valnum = val;
- }
-
- pre_stats.insertions++;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Inserted ");
- print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (res), 0);
- }
-
- return res;
-}
-
-class eliminate_dom_walker : public dom_walker
-{
-public:
- eliminate_dom_walker (cdi_direction direction, bool do_pre_)
- : dom_walker (direction), do_pre (do_pre_) {}
-
- virtual edge before_dom_children (basic_block);
- virtual void after_dom_children (basic_block);
-
- bool do_pre;
-};
-
-/* Perform elimination for the basic-block B during the domwalk. */
-
-edge
-eliminate_dom_walker::before_dom_children (basic_block b)
-{
- /* Mark new bb. */
- el_avail_stack.safe_push (NULL_TREE);
-
- /* Skip unreachable blocks marked unreachable during the SCCVN domwalk. */
- edge_iterator ei;
- edge e;
- FOR_EACH_EDGE (e, ei, b->preds)
- if (e->flags & EDGE_EXECUTABLE)
- break;
- if (! e)
- return NULL;
-
- for (gphi_iterator gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
- {
- gphi *phi = gsi.phi ();
- tree res = PHI_RESULT (phi);
-
- if (virtual_operand_p (res))
- {
- gsi_next (&gsi);
- continue;
- }
-
- tree sprime = eliminate_avail (res);
- if (sprime
- && sprime != res)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Replaced redundant PHI node defining ");
- print_generic_expr (dump_file, res);
- fprintf (dump_file, " with ");
- print_generic_expr (dump_file, sprime);
- fprintf (dump_file, "\n");
- }
-
- /* If we inserted this PHI node ourself, it's not an elimination. */
- if (inserted_exprs
- && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
- pre_stats.phis--;
- else
- pre_stats.eliminations++;
-
- /* If we will propagate into all uses don't bother to do
- anything. */
- if (may_propagate_copy (res, sprime))
- {
- /* Mark the PHI for removal. */
- el_to_remove.safe_push (phi);
- gsi_next (&gsi);
- continue;
- }
-
- remove_phi_node (&gsi, false);
-
- if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
- sprime = fold_convert (TREE_TYPE (res), sprime);
- gimple *stmt = gimple_build_assign (res, sprime);
- gimple_stmt_iterator gsi2 = gsi_after_labels (b);
- gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
- continue;
- }
-
- eliminate_push_avail (res);
- gsi_next (&gsi);
- }
-
- for (gimple_stmt_iterator gsi = gsi_start_bb (b);
- !gsi_end_p (gsi);
- gsi_next (&gsi))
- {
- tree sprime = NULL_TREE;
- gimple *stmt = gsi_stmt (gsi);
- tree lhs = gimple_get_lhs (stmt);
- if (lhs && TREE_CODE (lhs) == SSA_NAME
- && !gimple_has_volatile_ops (stmt)
- /* See PR43491. Do not replace a global register variable when
- it is a the RHS of an assignment. Do replace local register
- variables since gcc does not guarantee a local variable will
- be allocated in register.
- ??? The fix isn't effective here. This should instead
- be ensured by not value-numbering them the same but treating
- them like volatiles? */
- && !(gimple_assign_single_p (stmt)
- && (TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
- && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))
- && is_global_var (gimple_assign_rhs1 (stmt)))))
- {
- sprime = eliminate_avail (lhs);
- if (!sprime)
- {
- /* If there is no existing usable leader but SCCVN thinks
- it has an expression it wants to use as replacement,
- insert that. */
- tree val = VN_INFO (lhs)->valnum;
- if (val != VN_TOP
- && TREE_CODE (val) == SSA_NAME
- && VN_INFO (val)->needs_insertion
- && VN_INFO (val)->expr != NULL
- && (sprime = eliminate_insert (&gsi, val)) != NULL_TREE)
- eliminate_push_avail (sprime);
- }
-
- /* If this now constitutes a copy duplicate points-to
- and range info appropriately. This is especially
- important for inserted code. See tree-ssa-copy.c
- for similar code. */
- if (sprime
- && TREE_CODE (sprime) == SSA_NAME)
- {
- basic_block sprime_b = gimple_bb (SSA_NAME_DEF_STMT (sprime));
- if (POINTER_TYPE_P (TREE_TYPE (lhs))
- && VN_INFO_PTR_INFO (lhs)
- && ! VN_INFO_PTR_INFO (sprime))
- {
- duplicate_ssa_name_ptr_info (sprime,
- VN_INFO_PTR_INFO (lhs));
- if (b != sprime_b)
- mark_ptr_info_alignment_unknown
- (SSA_NAME_PTR_INFO (sprime));
- }
- else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
- && VN_INFO_RANGE_INFO (lhs)
- && ! VN_INFO_RANGE_INFO (sprime)
- && b == sprime_b)
- duplicate_ssa_name_range_info (sprime,
- VN_INFO_RANGE_TYPE (lhs),
- VN_INFO_RANGE_INFO (lhs));
- }
-
- /* Inhibit the use of an inserted PHI on a loop header when
- the address of the memory reference is a simple induction
- variable. In other cases the vectorizer won't do anything
- anyway (either it's loop invariant or a complicated
- expression). */
- if (sprime
- && TREE_CODE (sprime) == SSA_NAME
- && do_pre
- && (flag_tree_loop_vectorize || flag_tree_parallelize_loops > 1)
- && loop_outer (b->loop_father)
- && has_zero_uses (sprime)
- && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (sprime))
- && gimple_assign_load_p (stmt))
- {
- gimple *def_stmt = SSA_NAME_DEF_STMT (sprime);
- basic_block def_bb = gimple_bb (def_stmt);
- if (gimple_code (def_stmt) == GIMPLE_PHI
- && def_bb->loop_father->header == def_bb)
- {
- loop_p loop = def_bb->loop_father;
- ssa_op_iter iter;
- tree op;
- bool found = false;
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
- {
- affine_iv iv;
- def_bb = gimple_bb (SSA_NAME_DEF_STMT (op));
- if (def_bb
- && flow_bb_inside_loop_p (loop, def_bb)
- && simple_iv (loop, loop, op, &iv, true))
- {
- found = true;
- break;
- }
- }
- if (found)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Not replacing ");
- print_gimple_expr (dump_file, stmt, 0);
- fprintf (dump_file, " with ");
- print_generic_expr (dump_file, sprime);
- fprintf (dump_file, " which would add a loop"
- " carried dependence to loop %d\n",
- loop->num);
- }
- /* Don't keep sprime available. */
- sprime = NULL_TREE;
- }
- }
- }
-
- if (sprime)
- {
- /* If we can propagate the value computed for LHS into
- all uses don't bother doing anything with this stmt. */
- if (may_propagate_copy (lhs, sprime))
- {
- /* Mark it for removal. */
- el_to_remove.safe_push (stmt);
-
- /* ??? Don't count copy/constant propagations. */
- if (gimple_assign_single_p (stmt)
- && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
- || gimple_assign_rhs1 (stmt) == sprime))
- continue;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Replaced ");
- print_gimple_expr (dump_file, stmt, 0);
- fprintf (dump_file, " with ");
- print_generic_expr (dump_file, sprime);
- fprintf (dump_file, " in all uses of ");
- print_gimple_stmt (dump_file, stmt, 0);
- }
-
- pre_stats.eliminations++;
- continue;
- }
-
- /* If this is an assignment from our leader (which
- happens in the case the value-number is a constant)
- then there is nothing to do. */
- if (gimple_assign_single_p (stmt)
- && sprime == gimple_assign_rhs1 (stmt))
- continue;
-
- /* Else replace its RHS. */
- bool can_make_abnormal_goto
- = is_gimple_call (stmt)
- && stmt_can_make_abnormal_goto (stmt);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Replaced ");
- print_gimple_expr (dump_file, stmt, 0);
- fprintf (dump_file, " with ");
- print_generic_expr (dump_file, sprime);
- fprintf (dump_file, " in ");
- print_gimple_stmt (dump_file, stmt, 0);
- }
-
- pre_stats.eliminations++;
- gimple *orig_stmt = stmt;
- if (!useless_type_conversion_p (TREE_TYPE (lhs),
- TREE_TYPE (sprime)))
- sprime = fold_convert (TREE_TYPE (lhs), sprime);
- tree vdef = gimple_vdef (stmt);
- tree vuse = gimple_vuse (stmt);
- propagate_tree_value_into_stmt (&gsi, sprime);
- stmt = gsi_stmt (gsi);
- update_stmt (stmt);
- if (vdef != gimple_vdef (stmt))
- VN_INFO (vdef)->valnum = vuse;
-
- /* If we removed EH side-effects from the statement, clean
- its EH information. */
- if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
- {
- bitmap_set_bit (need_eh_cleanup,
- gimple_bb (stmt)->index);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Removed EH side-effects.\n");
- }
-
- /* Likewise for AB side-effects. */
- if (can_make_abnormal_goto
- && !stmt_can_make_abnormal_goto (stmt))
- {
- bitmap_set_bit (need_ab_cleanup,
- gimple_bb (stmt)->index);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Removed AB side-effects.\n");
- }
-
- continue;
- }
- }
-
- /* If the statement is a scalar store, see if the expression
- has the same value number as its rhs. If so, the store is
- dead. */
- if (gimple_assign_single_p (stmt)
- && !gimple_has_volatile_ops (stmt)
- && !is_gimple_reg (gimple_assign_lhs (stmt))
- && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
- || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
- {
- tree val;
- tree rhs = gimple_assign_rhs1 (stmt);
- vn_reference_t vnresult;
- val = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_WALKREWRITE,
- &vnresult, false);
- if (TREE_CODE (rhs) == SSA_NAME)
- rhs = VN_INFO (rhs)->valnum;
- if (val
- && operand_equal_p (val, rhs, 0))
- {
- /* We can only remove the later store if the former aliases
- at least all accesses the later one does or if the store
- was to readonly memory storing the same value. */
- alias_set_type set = get_alias_set (lhs);
- if (! vnresult
- || vnresult->set == set
- || alias_set_subset_of (set, vnresult->set))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Deleted redundant store ");
- print_gimple_stmt (dump_file, stmt, 0);
- }
-
- /* Queue stmt for removal. */
- el_to_remove.safe_push (stmt);
- continue;
- }
- }
- }
-
- /* If this is a control statement value numbering left edges
- unexecuted on force the condition in a way consistent with
- that. */
- if (gcond *cond = dyn_cast <gcond *> (stmt))
- {
- if ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE)
- ^ (EDGE_SUCC (b, 1)->flags & EDGE_EXECUTABLE))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Removing unexecutable edge from ");
- print_gimple_stmt (dump_file, stmt, 0);
- }
- if (((EDGE_SUCC (b, 0)->flags & EDGE_TRUE_VALUE) != 0)
- == ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE) != 0))
- gimple_cond_make_true (cond);
- else
- gimple_cond_make_false (cond);
- update_stmt (cond);
- el_todo |= TODO_cleanup_cfg;
- continue;
- }
- }
-
- bool can_make_abnormal_goto = stmt_can_make_abnormal_goto (stmt);
- bool was_noreturn = (is_gimple_call (stmt)
- && gimple_call_noreturn_p (stmt));
- tree vdef = gimple_vdef (stmt);
- tree vuse = gimple_vuse (stmt);
-
- /* If we didn't replace the whole stmt (or propagate the result
- into all uses), replace all uses on this stmt with their
- leaders. */
- bool modified = false;
- use_operand_p use_p;
- ssa_op_iter iter;
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
- {
- tree use = USE_FROM_PTR (use_p);
- /* ??? The call code above leaves stmt operands un-updated. */
- if (TREE_CODE (use) != SSA_NAME)
- continue;
- tree sprime = eliminate_avail (use);
- if (sprime && sprime != use
- && may_propagate_copy (use, sprime)
- /* We substitute into debug stmts to avoid excessive
- debug temporaries created by removed stmts, but we need
- to avoid doing so for inserted sprimes as we never want
- to create debug temporaries for them. */
- && (!inserted_exprs
- || TREE_CODE (sprime) != SSA_NAME
- || !is_gimple_debug (stmt)
- || !bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (sprime))))
- {
- propagate_value (use_p, sprime);
- modified = true;
- }
- }
-
- /* Fold the stmt if modified, this canonicalizes MEM_REFs we propagated
- into which is a requirement for the IPA devirt machinery. */
- gimple *old_stmt = stmt;
- if (modified)
- {
- /* If a formerly non-invariant ADDR_EXPR is turned into an
- invariant one it was on a separate stmt. */
- if (gimple_assign_single_p (stmt)
- && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
- recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
- gimple_stmt_iterator prev = gsi;
- gsi_prev (&prev);
- if (fold_stmt (&gsi))
- {
- /* fold_stmt may have created new stmts inbetween
- the previous stmt and the folded stmt. Mark
- all defs created there as varying to not confuse
- the SCCVN machinery as we're using that even during
- elimination. */
- if (gsi_end_p (prev))
- prev = gsi_start_bb (b);
- else
- gsi_next (&prev);
- if (gsi_stmt (prev) != gsi_stmt (gsi))
- do
- {
- tree def;
- ssa_op_iter dit;
- FOR_EACH_SSA_TREE_OPERAND (def, gsi_stmt (prev),
- dit, SSA_OP_ALL_DEFS)
- /* As existing DEFs may move between stmts
- we have to guard VN_INFO_GET. */
- if (! has_VN_INFO (def))
- VN_INFO_GET (def)->valnum = def;
- if (gsi_stmt (prev) == gsi_stmt (gsi))
- break;
- gsi_next (&prev);
- }
- while (1);
- }
- stmt = gsi_stmt (gsi);
- /* In case we folded the stmt away schedule the NOP for removal. */
- if (gimple_nop_p (stmt))
- el_to_remove.safe_push (stmt);
- }
-
- /* Visit indirect calls and turn them into direct calls if
- possible using the devirtualization machinery. Do this before
- checking for required EH/abnormal/noreturn cleanup as devird
- may expose more of those. */
- if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
- {
- tree fn = gimple_call_fn (call_stmt);
- if (fn
- && flag_devirtualize
- && virtual_method_call_p (fn))
- {
- tree otr_type = obj_type_ref_class (fn);
- unsigned HOST_WIDE_INT otr_tok
- = tree_to_uhwi (OBJ_TYPE_REF_TOKEN (fn));
- tree instance;
- ipa_polymorphic_call_context context (current_function_decl,
- fn, stmt, &instance);
- context.get_dynamic_type (instance, OBJ_TYPE_REF_OBJECT (fn),
- otr_type, stmt);
- bool final;
- vec <cgraph_node *> targets
- = possible_polymorphic_call_targets (obj_type_ref_class (fn),
- otr_tok, context, &final);
- if (dump_file)
- dump_possible_polymorphic_call_targets (dump_file,
- obj_type_ref_class (fn),
- otr_tok, context);
- if (final && targets.length () <= 1 && dbg_cnt (devirt))
- {
- tree fn;
- if (targets.length () == 1)
- fn = targets[0]->decl;
- else
- fn = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
- if (dump_enabled_p ())
- {
- location_t loc = gimple_location (stmt);
- dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
- "converting indirect call to "
- "function %s\n",
- lang_hooks.decl_printable_name (fn, 2));
- }
- gimple_call_set_fndecl (call_stmt, fn);
- /* If changing the call to __builtin_unreachable
- or similar noreturn function, adjust gimple_call_fntype
- too. */
- if (gimple_call_noreturn_p (call_stmt)
- && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn)))
- && TYPE_ARG_TYPES (TREE_TYPE (fn))
- && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn)))
- == void_type_node))
- gimple_call_set_fntype (call_stmt, TREE_TYPE (fn));
- maybe_remove_unused_call_args (cfun, call_stmt);
- modified = true;
- }
- }
- }
-
- if (modified)
- {
- /* When changing a call into a noreturn call, cfg cleanup
- is needed to fix up the noreturn call. */
- if (!was_noreturn
- && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
- el_to_fixup.safe_push (stmt);
- /* When changing a condition or switch into one we know what
- edge will be executed, schedule a cfg cleanup. */
- if ((gimple_code (stmt) == GIMPLE_COND
- && (gimple_cond_true_p (as_a <gcond *> (stmt))
- || gimple_cond_false_p (as_a <gcond *> (stmt))))
- || (gimple_code (stmt) == GIMPLE_SWITCH
- && TREE_CODE (gimple_switch_index
- (as_a <gswitch *> (stmt))) == INTEGER_CST))
- el_todo |= TODO_cleanup_cfg;
- /* If we removed EH side-effects from the statement, clean
- its EH information. */
- if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
- {
- bitmap_set_bit (need_eh_cleanup,
- gimple_bb (stmt)->index);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Removed EH side-effects.\n");
- }
- /* Likewise for AB side-effects. */
- if (can_make_abnormal_goto
- && !stmt_can_make_abnormal_goto (stmt))
- {
- bitmap_set_bit (need_ab_cleanup,
- gimple_bb (stmt)->index);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Removed AB side-effects.\n");
- }
- update_stmt (stmt);
- if (vdef != gimple_vdef (stmt))
- VN_INFO (vdef)->valnum = vuse;
- }
-
- /* Make new values available - for fully redundant LHS we
- continue with the next stmt above and skip this. */
- def_operand_p defp;
- FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_DEF)
- eliminate_push_avail (DEF_FROM_PTR (defp));
- }
-
- /* Replace destination PHI arguments. */
- FOR_EACH_EDGE (e, ei, b->succs)
- if (e->flags & EDGE_EXECUTABLE)
- for (gphi_iterator gsi = gsi_start_phis (e->dest);
- !gsi_end_p (gsi);
- gsi_next (&gsi))
- {
- gphi *phi = gsi.phi ();
- use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
- tree arg = USE_FROM_PTR (use_p);
- if (TREE_CODE (arg) != SSA_NAME
- || virtual_operand_p (arg))
- continue;
- tree sprime = eliminate_avail (arg);
- if (sprime && may_propagate_copy (arg, sprime))
- propagate_value (use_p, sprime);
- }
- return NULL;
-}
-
-/* Make no longer available leaders no longer available. */
-
-void
-eliminate_dom_walker::after_dom_children (basic_block)
-{
- tree entry;
- while ((entry = el_avail_stack.pop ()) != NULL_TREE)
- {
- tree valnum = VN_INFO (entry)->valnum;
- tree old = el_avail[SSA_NAME_VERSION (valnum)];
- if (old == entry)
- el_avail[SSA_NAME_VERSION (valnum)] = NULL_TREE;
- else
- el_avail[SSA_NAME_VERSION (valnum)] = entry;
- }
-}
-
-/* Eliminate fully redundant computations. */
-
-static unsigned int
-eliminate (bool do_pre)
-{
- need_eh_cleanup = BITMAP_ALLOC (NULL);
- need_ab_cleanup = BITMAP_ALLOC (NULL);
-
- el_to_remove.create (0);
- el_to_fixup.create (0);
- el_todo = 0;
- el_avail.create (num_ssa_names);
- el_avail_stack.create (0);
-
- eliminate_dom_walker (CDI_DOMINATORS,
- do_pre).walk (cfun->cfg->x_entry_block_ptr);
-
- el_avail.release ();
- el_avail_stack.release ();
-
- return el_todo;
-}
-
-/* Perform CFG cleanups made necessary by elimination. */
-
-static unsigned
-fini_eliminate (void)
-{
- gimple_stmt_iterator gsi;
- gimple *stmt;
- unsigned todo = 0;
-
- /* We cannot remove stmts during BB walk, especially not release SSA
- names there as this confuses the VN machinery. The stmts ending
- up in el_to_remove are either stores or simple copies.
- Remove stmts in reverse order to make debug stmt creation possible. */
- while (!el_to_remove.is_empty ())
- {
- stmt = el_to_remove.pop ();
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Removing dead stmt ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
- }
-
- gsi = gsi_for_stmt (stmt);
- if (gimple_code (stmt) == GIMPLE_PHI)
- remove_phi_node (&gsi, true);
- else
- {
- basic_block bb = gimple_bb (stmt);
- unlink_stmt_vdef (stmt);
- if (gsi_remove (&gsi, true))
- bitmap_set_bit (need_eh_cleanup, bb->index);
- if (is_gimple_call (stmt) && stmt_can_make_abnormal_goto (stmt))
- bitmap_set_bit (need_ab_cleanup, bb->index);
- release_defs (stmt);
- }
-
- /* Removing a stmt may expose a forwarder block. */
- todo |= TODO_cleanup_cfg;
- }
- el_to_remove.release ();
-
- /* Fixup stmts that became noreturn calls. This may require splitting
- blocks and thus isn't possible during the dominator walk. Do this
- in reverse order so we don't inadvertedly remove a stmt we want to
- fixup by visiting a dominating now noreturn call first. */
- while (!el_to_fixup.is_empty ())
- {
- stmt = el_to_fixup.pop ();
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Fixing up noreturn call ");
- print_gimple_stmt (dump_file, stmt, 0);
- }
-
- if (fixup_noreturn_call (stmt))
- todo |= TODO_cleanup_cfg;
- }
- el_to_fixup.release ();
-
- bool do_eh_cleanup = !bitmap_empty_p (need_eh_cleanup);
- bool do_ab_cleanup = !bitmap_empty_p (need_ab_cleanup);
-
- if (do_eh_cleanup)
- gimple_purge_all_dead_eh_edges (need_eh_cleanup);
-
- if (do_ab_cleanup)
- gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup);
-
- BITMAP_FREE (need_eh_cleanup);
- BITMAP_FREE (need_ab_cleanup);
-
- if (do_eh_cleanup || do_ab_cleanup)
- todo |= TODO_cleanup_cfg;
- return todo;
-}
-
-/* Cheap DCE of a known set of possibly dead stmts.
-
- Because we don't follow exactly the standard PRE algorithm, and decide not
- to insert PHI nodes sometimes, and because value numbering of casts isn't
- perfect, we sometimes end up inserting dead code. This simple DCE-like
- pass removes any insertions we made that weren't actually used. */
-
-static void
-remove_dead_inserted_code (void)
-{
- /* ??? Re-use inserted_exprs as worklist not only as initial set.
- This may end up removing non-inserted code as well. If we
- keep inserted_exprs unchanged we could restrict new worklist
- elements to members of inserted_exprs. */
- bitmap worklist = inserted_exprs;
- while (! bitmap_empty_p (worklist))
- {
- /* Pop item. */
- unsigned i = bitmap_first_set_bit (worklist);
- bitmap_clear_bit (worklist, i);
-
- tree def = ssa_name (i);
- /* Removed by somebody else or still in use. */
- if (! def || ! has_zero_uses (def))
- continue;
-
- gimple *t = SSA_NAME_DEF_STMT (def);
- if (gimple_has_side_effects (t))
- continue;
-
- /* Add uses to the worklist. */
- ssa_op_iter iter;
- use_operand_p use_p;
- FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
- {
- tree use = USE_FROM_PTR (use_p);
- if (TREE_CODE (use) == SSA_NAME
- && ! SSA_NAME_IS_DEFAULT_DEF (use))
- bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
- }
-
- /* Remove stmt. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Removing unnecessary insertion:");
- print_gimple_stmt (dump_file, t, 0);
- }
- gimple_stmt_iterator gsi = gsi_for_stmt (t);
- if (gimple_code (t) == GIMPLE_PHI)
- remove_phi_node (&gsi, true);
- else
- {
- gsi_remove (&gsi, true);
- release_defs (t);
- }
- }
-}
-
-
/* Initialize data structures used by PRE. */
static void
fini_pre ()
{
value_expressions.release ();
+ expressions.release ();
BITMAP_FREE (inserted_exprs);
bitmap_obstack_release (&grand_bitmap_obstack);
bitmap_set_pool.release ();
loop_optimizer_init may create new phis, etc. */
loop_optimizer_init (LOOPS_NORMAL);
split_critical_edges ();
+ scev_initialize ();
run_scc_vn (VN_WALK);
init_pre ();
- scev_initialize ();
-
- /* Collect and value number expressions computed in each basic block. */
- compute_avail ();
/* Insert can get quite slow on an incredibly large number of basic
blocks due to some quadratic behavior. Until this behavior is
fixed, don't run it when he have an incredibly large number of
bb's. If we aren't going to run insert, there is no point in
- computing ANTIC, either, even though it's plenty fast. */
+ computing ANTIC, either, even though it's plenty fast nor do
+ we require AVAIL. */
if (n_basic_blocks_for_fn (fun) < 4000)
{
+ compute_avail ();
compute_antic ();
insert ();
}
not keeping virtual operands up-to-date. */
gcc_assert (!need_ssa_update_p (fun));
- /* Remove all the redundant expressions. */
- todo |= eliminate (true);
-
statistics_counter_event (fun, "Insertions", pre_stats.insertions);
statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
statistics_counter_event (fun, "New PHIs", pre_stats.phis);
- statistics_counter_event (fun, "Eliminated", pre_stats.eliminations);
- clear_expression_ids ();
+ /* Remove all the redundant expressions. */
+ todo |= vn_eliminate (inserted_exprs);
+
+ /* Because we don't follow exactly the standard PRE algorithm, and decide not
+ to insert PHI nodes sometimes, and because value numbering of casts isn't
+ perfect, we sometimes end up inserting dead code. This simple DCE-like
+ pass removes any insertions we made that weren't actually used. */
+ simple_dce_from_worklist (inserted_exprs);
- scev_finalize ();
- todo |= fini_eliminate ();
- remove_dead_inserted_code ();
fini_pre ();
+
+ scev_finalize ();
loop_optimizer_finalize ();
/* Restore SSA info before tail-merging as that resets it as well. */
{
return new pass_pre (ctxt);
}
-
-namespace {
-
-const pass_data pass_data_fre =
-{
- GIMPLE_PASS, /* type */
- "fre", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- TV_TREE_FRE, /* tv_id */
- ( PROP_cfg | PROP_ssa ), /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0, /* todo_flags_finish */
-};
-
-class pass_fre : public gimple_opt_pass
-{
-public:
- pass_fre (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_fre, ctxt)
- {}
-
- /* opt_pass methods: */
- opt_pass * clone () { return new pass_fre (m_ctxt); }
- virtual bool gate (function *) { return flag_tree_fre != 0; }
- virtual unsigned int execute (function *);
-
-}; // class pass_fre
-
-unsigned int
-pass_fre::execute (function *fun)
-{
- unsigned int todo = 0;
-
- run_scc_vn (VN_WALKREWRITE);
-
- memset (&pre_stats, 0, sizeof (pre_stats));
-
- /* Remove all the redundant expressions. */
- todo |= eliminate (false);
-
- todo |= fini_eliminate ();
-
- scc_vn_restore_ssa_info ();
- free_scc_vn ();
-
- statistics_counter_event (fun, "Insertions", pre_stats.insertions);
- statistics_counter_event (fun, "Eliminated", pre_stats.eliminations);
-
- return todo;
-}
-
-} // anon namespace
-
-gimple_opt_pass *
-make_pass_fre (gcc::context *ctxt)
-{
- return new pass_fre (ctxt);
-}
projects / gcc.git / blobdiff