/* SSA Dominator optimizations for trees
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
#include "tm.h"
#include "tree.h"
#include "flags.h"
-#include "rtl.h"
#include "tm_p.h"
-#include "ggc.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "output.h"
-#include "expr.h"
#include "function.h"
-#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-flow.h"
#include "domwalk.h"
-#include "real.h"
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "langhooks.h"
EXPR_SINGLE,
EXPR_UNARY,
EXPR_BINARY,
- EXPR_CALL
+ EXPR_TERNARY,
+ EXPR_CALL,
+ EXPR_PHI
};
struct hashable_expr
union {
struct { tree rhs; } single;
struct { enum tree_code op; tree opnd; } unary;
- struct { enum tree_code op; tree opnd0; tree opnd1; } binary;
- struct { tree fn; bool pure; size_t nargs; tree *args; } call;
+ struct { enum tree_code op; tree opnd0, opnd1; } binary;
+ struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary;
+ struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call;
+ struct { size_t nargs; tree *args; } phi;
} ops;
};
/* Structure for recording known values of a conditional expression
at the exits from its block. */
-struct cond_equivalence
+typedef struct cond_equivalence_s
{
struct hashable_expr cond;
tree value;
-};
+} cond_equivalence;
+
+DEF_VEC_O(cond_equivalence);
+DEF_VEC_ALLOC_O(cond_equivalence,heap);
/* Structure for recording edge equivalences as well as any pending
edge redirections during the dominator optimizer.
Computing and storing the edge equivalences instead of creating
them on-demand can save significant amounts of time, particularly
- for pathological cases involving switch statements.
+ for pathological cases involving switch statements.
These structures live for a single iteration of the dominator
optimizer in the edge's AUX field. At the end of an iteration we
tree rhs;
/* Traversing an edge may also indicate one or more particular conditions
- are true or false. The number of recorded conditions can vary, but
- can be determined by the condition's code. So we have an array
- and its maximum index rather than use a varray. */
- struct cond_equivalence *cond_equivalences;
- unsigned int max_cond_equivalences;
+ are true or false. */
+ VEC(cond_equivalence, heap) *cond_equivalences;
};
/* Hash table with expressions made available during the renaming process.
static hashval_t real_avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
-static void record_cond (struct cond_equivalence *);
+static void record_cond (cond_equivalence *);
static void record_const_or_copy (tree, tree);
static void record_equality (tree, tree);
static void record_equivalences_from_phis (basic_block);
{
enum tree_code subcode = gimple_assign_rhs_code (stmt);
- expr->type = NULL_TREE;
-
switch (get_gimple_rhs_class (subcode))
{
case GIMPLE_SINGLE_RHS:
- expr->kind = EXPR_SINGLE;
- expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
- break;
+ expr->kind = EXPR_SINGLE;
+ expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
+ expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
+ break;
case GIMPLE_UNARY_RHS:
- expr->kind = EXPR_UNARY;
+ expr->kind = EXPR_UNARY;
expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
- expr->ops.unary.op = subcode;
- expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
- break;
+ expr->ops.unary.op = subcode;
+ expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
+ break;
case GIMPLE_BINARY_RHS:
- expr->kind = EXPR_BINARY;
+ expr->kind = EXPR_BINARY;
+ expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
+ expr->ops.binary.op = subcode;
+ expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
+ expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
+ break;
+ case GIMPLE_TERNARY_RHS:
+ expr->kind = EXPR_TERNARY;
expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
- expr->ops.binary.op = subcode;
- expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
- expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
- break;
+ expr->ops.ternary.op = subcode;
+ expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt);
+ expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt);
+ expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt);
+ break;
default:
gcc_unreachable ();
}
expr->type = TREE_TYPE (gimple_call_lhs (stmt));
expr->kind = EXPR_CALL;
- expr->ops.call.fn = gimple_call_fn (stmt);
+ expr->ops.call.fn_from = stmt;
if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
expr->ops.call.pure = true;
- else
+ else
expr->ops.call.pure = false;
expr->ops.call.nargs = nargs;
- expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree));
+ expr->ops.call.args = XCNEWVEC (tree, nargs);
for (i = 0; i < nargs; i++)
expr->ops.call.args[i] = gimple_call_arg (stmt, i);
}
expr->kind = EXPR_SINGLE;
expr->ops.single.rhs = gimple_goto_dest (stmt);
}
+ else if (code == GIMPLE_PHI)
+ {
+ size_t nargs = gimple_phi_num_args (stmt);
+ size_t i;
+
+ expr->type = TREE_TYPE (gimple_phi_result (stmt));
+ expr->kind = EXPR_PHI;
+ expr->ops.phi.nargs = nargs;
+ expr->ops.phi.args = XCNEWVEC (tree, nargs);
+
+ for (i = 0; i < nargs; i++)
+ expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
+ }
else
gcc_unreachable ();
initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
{
expr->type = boolean_type_node;
-
+
if (COMPARISON_CLASS_P (cond))
{
expr->kind = EXPR_BINARY;
expr1->ops.unary.opnd, 0);
case EXPR_BINARY:
- {
- if (expr0->ops.binary.op != expr1->ops.binary.op)
- return false;
-
- if (operand_equal_p (expr0->ops.binary.opnd0,
- expr1->ops.binary.opnd0, 0)
- && operand_equal_p (expr0->ops.binary.opnd1,
- expr1->ops.binary.opnd1, 0))
- return true;
-
- /* For commutative ops, allow the other order. */
- return (commutative_tree_code (expr0->ops.binary.op)
- && operand_equal_p (expr0->ops.binary.opnd0,
- expr1->ops.binary.opnd1, 0)
- && operand_equal_p (expr0->ops.binary.opnd1,
- expr1->ops.binary.opnd0, 0));
- }
+ if (expr0->ops.binary.op != expr1->ops.binary.op)
+ return false;
+
+ if (operand_equal_p (expr0->ops.binary.opnd0,
+ expr1->ops.binary.opnd0, 0)
+ && operand_equal_p (expr0->ops.binary.opnd1,
+ expr1->ops.binary.opnd1, 0))
+ return true;
+
+ /* For commutative ops, allow the other order. */
+ return (commutative_tree_code (expr0->ops.binary.op)
+ && operand_equal_p (expr0->ops.binary.opnd0,
+ expr1->ops.binary.opnd1, 0)
+ && operand_equal_p (expr0->ops.binary.opnd1,
+ expr1->ops.binary.opnd0, 0));
+
+ case EXPR_TERNARY:
+ if (expr0->ops.ternary.op != expr1->ops.ternary.op
+ || !operand_equal_p (expr0->ops.ternary.opnd2,
+ expr1->ops.ternary.opnd2, 0))
+ return false;
+
+ if (operand_equal_p (expr0->ops.ternary.opnd0,
+ expr1->ops.ternary.opnd0, 0)
+ && operand_equal_p (expr0->ops.ternary.opnd1,
+ expr1->ops.ternary.opnd1, 0))
+ return true;
+
+ /* For commutative ops, allow the other order. */
+ return (commutative_ternary_tree_code (expr0->ops.ternary.op)
+ && operand_equal_p (expr0->ops.ternary.opnd0,
+ expr1->ops.ternary.opnd1, 0)
+ && operand_equal_p (expr0->ops.ternary.opnd1,
+ expr1->ops.ternary.opnd0, 0));
case EXPR_CALL:
{
/* If the calls are to different functions, then they
clearly cannot be equal. */
- if (! operand_equal_p (expr0->ops.call.fn,
- expr1->ops.call.fn, 0))
+ if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
+ expr1->ops.call.fn_from))
return false;
if (! expr0->ops.call.pure)
return true;
}
-
+
+ case EXPR_PHI:
+ {
+ size_t i;
+
+ if (expr0->ops.phi.nargs != expr1->ops.phi.nargs)
+ return false;
+
+ for (i = 0; i < expr0->ops.phi.nargs; i++)
+ if (! operand_equal_p (expr0->ops.phi.args[i],
+ expr1->ops.phi.args[i], 0))
+ return false;
+
+ return true;
+ }
+
default:
gcc_unreachable ();
}
case EXPR_BINARY:
val = iterative_hash_object (expr->ops.binary.op, val);
if (commutative_tree_code (expr->ops.binary.op))
- val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
- expr->ops.binary.opnd1, val);
+ val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
+ expr->ops.binary.opnd1, val);
else
{
val = iterative_hash_expr (expr->ops.binary.opnd0, val);
}
break;
+ case EXPR_TERNARY:
+ val = iterative_hash_object (expr->ops.ternary.op, val);
+ if (commutative_ternary_tree_code (expr->ops.ternary.op))
+ val = iterative_hash_exprs_commutative (expr->ops.ternary.opnd0,
+ expr->ops.ternary.opnd1, val);
+ else
+ {
+ val = iterative_hash_expr (expr->ops.ternary.opnd0, val);
+ val = iterative_hash_expr (expr->ops.ternary.opnd1, val);
+ }
+ val = iterative_hash_expr (expr->ops.ternary.opnd2, val);
+ break;
+
case EXPR_CALL:
{
size_t i;
enum tree_code code = CALL_EXPR;
+ gimple fn_from;
val = iterative_hash_object (code, val);
- val = iterative_hash_expr (expr->ops.call.fn, val);
+ fn_from = expr->ops.call.fn_from;
+ if (gimple_call_internal_p (fn_from))
+ val = iterative_hash_hashval_t
+ ((hashval_t) gimple_call_internal_fn (fn_from), val);
+ else
+ val = iterative_hash_expr (gimple_call_fn (fn_from), val);
for (i = 0; i < expr->ops.call.nargs; i++)
val = iterative_hash_expr (expr->ops.call.args[i], val);
}
break;
-
+
+ case EXPR_PHI:
+ {
+ size_t i;
+
+ for (i = 0; i < expr->ops.phi.nargs; i++)
+ val = iterative_hash_expr (expr->ops.phi.args[i], val);
+ }
+ break;
+
default:
gcc_unreachable ();
}
print_generic_expr (stream, element->lhs, 0);
fprintf (stream, " = ");
}
-
+
switch (element->expr.kind)
{
case EXPR_SINGLE:
print_generic_expr (stream, element->expr.ops.binary.opnd1, 0);
break;
+ case EXPR_TERNARY:
+ fprintf (stream, " %s <", tree_code_name[element->expr.ops.ternary.op]);
+ print_generic_expr (stream, element->expr.ops.ternary.opnd0, 0);
+ fputs (", ", stream);
+ print_generic_expr (stream, element->expr.ops.ternary.opnd1, 0);
+ fputs (", ", stream);
+ print_generic_expr (stream, element->expr.ops.ternary.opnd2, 0);
+ fputs (">", stream);
+ break;
+
case EXPR_CALL:
{
size_t i;
size_t nargs = element->expr.ops.call.nargs;
-
- print_generic_expr (stream, element->expr.ops.call.fn, 0);
+ gimple fn_from;
+
+ fn_from = element->expr.ops.call.fn_from;
+ if (gimple_call_internal_p (fn_from))
+ fputs (internal_fn_name (gimple_call_internal_fn (fn_from)),
+ stream);
+ else
+ print_generic_expr (stream, gimple_call_fn (fn_from), 0);
fprintf (stream, " (");
for (i = 0; i < nargs; i++)
{
fprintf (stream, ")");
}
break;
+
+ case EXPR_PHI:
+ {
+ size_t i;
+ size_t nargs = element->expr.ops.phi.nargs;
+
+ fprintf (stream, "PHI <");
+ for (i = 0; i < nargs; i++)
+ {
+ print_generic_expr (stream, element->expr.ops.phi.args[i], 0);
+ if (i + 1 < nargs)
+ fprintf (stream, ", ");
+ }
+ fprintf (stream, ">");
+ }
+ break;
}
fprintf (stream, "\n");
if (element->expr.kind == EXPR_CALL)
free (element->expr.ops.call.args);
+ if (element->expr.kind == EXPR_PHI)
+ free (element->expr.ops.phi.args);
+
free (element);
}
if (edge_info)
{
if (edge_info->cond_equivalences)
- free (edge_info->cond_equivalences);
+ VEC_free (cond_equivalence, heap, edge_info->cond_equivalences);
free (edge_info);
e->aux = NULL;
}
}
}
-/* Jump threading, redundancy elimination and const/copy propagation.
+/* Jump threading, redundancy elimination and const/copy propagation.
This pass may expose new symbols that need to be renamed into SSA. For
every new symbol exposed, its corresponding bit will be set in
for jump threading; this may include back edges that are not part of
a single loop. */
mark_dfs_back_edges ();
-
+
/* Recursively walk the dominator tree optimizing statements. */
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
gimple_stmt_iterator gsi;
basic_block bb;
FOR_EACH_BB (bb)
- {for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
update_stmt_if_modified (gsi_stmt (gsi));
}
}
EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
{
basic_block bb = BASIC_BLOCK (i);
- if (single_succ_p (bb) == 1
+ if (bb
+ && single_succ_p (bb)
&& (single_succ_edge (bb)->flags & EDGE_EH) == 0)
{
bitmap_clear_bit (need_eh_cleanup, i);
/* Free asserted bitmaps and stacks. */
BITMAP_FREE (need_eh_cleanup);
-
+
VEC_free (expr_hash_elt_t, heap, avail_exprs_stack);
VEC_free (tree, heap, const_and_copies_stack);
-
+
/* Free the value-handle array. */
threadedge_finalize_values ();
ssa_name_values = NULL;
return flag_tree_dom != 0;
}
-struct gimple_opt_pass pass_dominator =
+struct gimple_opt_pass pass_dominator =
{
{
GIMPLE_PASS,
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func
+ TODO_cleanup_cfg
| TODO_update_ssa
- | TODO_cleanup_cfg
- | TODO_verify_ssa /* todo_flags_finish */
+ | TODO_verify_ssa
+ | TODO_verify_flow /* todo_flags_finish */
}
};
record_equivalences_from_phis (basic_block bb)
{
gimple_stmt_iterator gsi;
-
+
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
{
tree lhs = edge_info->lhs;
tree rhs = edge_info->rhs;
- struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
+ cond_equivalence *eq;
if (lhs)
record_equality (lhs, rhs);
- if (cond_equivalences)
- for (i = 0; i < edge_info->max_cond_equivalences; i++)
- record_cond (&cond_equivalences[i]);
+ for (i = 0; VEC_iterate (cond_equivalence,
+ edge_info->cond_equivalences, i, eq); ++i)
+ record_cond (eq);
}
}
}
/* Dump SSA statistics on stderr. */
-void
+DEBUG_FUNCTION void
debug_dominator_optimization_stats (void)
{
dump_dominator_optimization_stats (stderr);
boolean value. */
static void
-record_cond (struct cond_equivalence *p)
+record_cond (cond_equivalence *p)
{
struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
void **slot;
}
/* Build a cond_equivalence record indicating that the comparison
- CODE holds between operands OP0 and OP1. */
-
+ CODE holds between operands OP0 and OP1 and push it to **P. */
+
static void
build_and_record_new_cond (enum tree_code code,
tree op0, tree op1,
- struct cond_equivalence *p)
+ VEC(cond_equivalence, heap) **p)
{
- struct hashable_expr *cond = &p->cond;
+ cond_equivalence c;
+ struct hashable_expr *cond = &c.cond;
gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
cond->ops.binary.opnd0 = op0;
cond->ops.binary.opnd1 = op1;
- p->value = boolean_true_node;
+ c.value = boolean_true_node;
+ VEC_safe_push (cond_equivalence, heap, *p, &c);
}
/* Record that COND is true and INVERTED is false into the edge information
record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
{
tree op0, op1;
+ cond_equivalence c;
if (!COMPARISON_CLASS_P (cond))
return;
case GT_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
- edge_info->max_cond_equivalences = 6;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 6);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
- &edge_info->cond_equivalences[4]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (LTGT_EXPR, op0, op1,
- &edge_info->cond_equivalences[5]);
- }
- else
- {
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
+ &edge_info->cond_equivalences);
}
build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
? LE_EXPR : GE_EXPR),
- op0, op1, &edge_info->cond_equivalences[2]);
+ op0, op1, &edge_info->cond_equivalences);
build_and_record_new_cond (NE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
case GE_EXPR:
case LE_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
- edge_info->max_cond_equivalences = 3;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 3);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
- }
- else
- {
- edge_info->max_cond_equivalences = 2;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
+ &edge_info->cond_equivalences);
}
break;
case EQ_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (op0)))
{
- edge_info->max_cond_equivalences = 5;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 5);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
- &edge_info->cond_equivalences[4]);
- }
- else
- {
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
+ &edge_info->cond_equivalences);
}
build_and_record_new_cond (LE_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (GE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
case UNORDERED_EXPR:
- edge_info->max_cond_equivalences = 8;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 8);
build_and_record_new_cond (NE_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNLE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNGE_EXPR, op0, op1,
- &edge_info->cond_equivalences[4]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNEQ_EXPR, op0, op1,
- &edge_info->cond_equivalences[5]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNLT_EXPR, op0, op1,
- &edge_info->cond_equivalences[6]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNGT_EXPR, op0, op1,
- &edge_info->cond_equivalences[7]);
+ &edge_info->cond_equivalences);
break;
case UNLT_EXPR:
case UNGT_EXPR:
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
? UNLE_EXPR : UNGE_EXPR),
- op0, op1, &edge_info->cond_equivalences[2]);
+ op0, op1, &edge_info->cond_equivalences);
build_and_record_new_cond (NE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
case UNEQ_EXPR:
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
build_and_record_new_cond (UNLE_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (UNGE_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
case LTGT_EXPR:
- edge_info->max_cond_equivalences = 4;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
build_and_record_new_cond (NE_EXPR, op0, op1,
- &edge_info->cond_equivalences[2]);
+ &edge_info->cond_equivalences);
build_and_record_new_cond (ORDERED_EXPR, op0, op1,
- &edge_info->cond_equivalences[3]);
+ &edge_info->cond_equivalences);
break;
default:
- edge_info->max_cond_equivalences = 2;
- edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
break;
}
/* Now store the original true and false conditions into the first
two slots. */
- initialize_expr_from_cond (cond, &edge_info->cond_equivalences[0].cond);
- edge_info->cond_equivalences[0].value = boolean_true_node;
+ initialize_expr_from_cond (cond, &c.cond);
+ c.value = boolean_true_node;
+ VEC_safe_push (cond_equivalence, heap, edge_info->cond_equivalences, &c);
/* It is possible for INVERTED to be the negation of a comparison,
and not a valid RHS or GIMPLE_COND condition. This happens because
invert_truthvalue may return such an expression when asked to invert
a floating-point comparison. These comparisons are not assumed to
obey the trichotomy law. */
- initialize_expr_from_cond (inverted, &edge_info->cond_equivalences[1].cond);
- edge_info->cond_equivalences[1].value = boolean_false_node;
+ initialize_expr_from_cond (inverted, &c.cond);
+ c.value = boolean_false_node;
+ VEC_safe_push (cond_equivalence, heap, edge_info->cond_equivalences, &c);
}
/* A helper function for record_const_or_copy and record_equality.
/* Returns true when STMT is a simple iv increment. It detects the
following situation:
-
+
i_1 = phi (..., i_2)
i_2 = i_1 +/- ... */
-static bool
+bool
simple_iv_increment_p (gimple stmt)
{
+ enum tree_code code;
tree lhs, preinc;
gimple phi;
size_t i;
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (gimple_assign_rhs_code (stmt) != PLUS_EXPR
- && gimple_assign_rhs_code (stmt) != MINUS_EXPR)
+ code = gimple_assign_rhs_code (stmt);
+ if (code != PLUS_EXPR
+ && code != MINUS_EXPR
+ && code != POINTER_PLUS_EXPR)
return false;
preinc = gimple_assign_rhs1 (stmt);
-
if (TREE_CODE (preinc) != SSA_NAME)
return false;
}
/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
- known value for that SSA_NAME (or NULL if no value is known).
+ known value for that SSA_NAME (or NULL if no value is known).
Propagate values from CONST_AND_COPIES into the PHI nodes of the
successors of BB. */
{
tree cond = build2 (code, boolean_type_node, op0, op1);
tree inverted = invert_truthvalue_loc (loc, cond);
+ bool can_infer_simple_equiv
+ = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
+ && real_zerop (op0));
struct edge_info *edge_info;
edge_info = allocate_edge_info (true_edge);
record_conditions (edge_info, cond, inverted);
- if (code == EQ_EXPR)
+ if (can_infer_simple_equiv && code == EQ_EXPR)
{
edge_info->lhs = op1;
edge_info->rhs = op0;
edge_info = allocate_edge_info (false_edge);
record_conditions (edge_info, inverted, cond);
- if (code == NE_EXPR)
+ if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
{
edge_info->lhs = op1;
edge_info->rhs = op0;
}
else if (TREE_CODE (op0) == SSA_NAME
- && (is_gimple_min_invariant (op1)
- || TREE_CODE (op1) == SSA_NAME))
+ && (TREE_CODE (op1) == SSA_NAME
+ || is_gimple_min_invariant (op1)))
{
tree cond = build2 (code, boolean_type_node, op0, op1);
tree inverted = invert_truthvalue_loc (loc, cond);
+ bool can_infer_simple_equiv
+ = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op1)))
+ && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1)));
struct edge_info *edge_info;
edge_info = allocate_edge_info (true_edge);
record_conditions (edge_info, cond, inverted);
- if (code == EQ_EXPR)
+ if (can_infer_simple_equiv && code == EQ_EXPR)
{
edge_info->lhs = op0;
edge_info->rhs = op1;
edge_info = allocate_edge_info (false_edge);
record_conditions (edge_info, inverted, cond);
- if (TREE_CODE (cond) == NE_EXPR)
+ if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
{
edge_info->lhs = op0;
edge_info->rhs = op1;
/* PHI nodes can create equivalences too. */
record_equivalences_from_phis (bb);
+ /* Create equivalences from redundant PHIs. PHIs are only truly
+ redundant when they exist in the same block, so push another
+ marker and unwind right afterwards. */
+ VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ eliminate_redundant_computations (&gsi);
+ remove_local_expressions_from_table ();
+
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
optimize_stmt (bb, gsi);
&& (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
&& potentially_threadable_block (single_succ (bb)))
{
+ /* Push a marker on the stack, which thread_across_edge expects
+ and will remove. */
+ VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
dom_thread_across_edge (walk_data, single_succ_edge (bb));
}
else if ((last = last_stmt (bb))
our equivalence tables. */
if (edge_info)
{
- struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
+ cond_equivalence *eq;
tree lhs = edge_info->lhs;
tree rhs = edge_info->rhs;
/* If we have 0 = COND or 1 = COND equivalences, record them
into our expression hash tables. */
- if (cond_equivalences)
- for (i = 0; i < edge_info->max_cond_equivalences; i++)
- record_cond (&cond_equivalences[i]);
+ for (i = 0; VEC_iterate (cond_equivalence,
+ edge_info->cond_equivalences, i, eq); ++i)
+ record_cond (eq);
}
dom_thread_across_edge (walk_data, true_edge);
our equivalence tables. */
if (edge_info)
{
- struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
+ cond_equivalence *eq;
tree lhs = edge_info->lhs;
tree rhs = edge_info->rhs;
/* If we have 0 = COND or 1 = COND equivalences, record them
into our expression hash tables. */
- if (cond_equivalences)
- for (i = 0; i < edge_info->max_cond_equivalences; i++)
- record_cond (&cond_equivalences[i]);
+ for (i = 0; VEC_iterate (cond_equivalence,
+ edge_info->cond_equivalences, i, eq); ++i)
+ record_cond (eq);
}
/* Now thread the edge. */
{
tree expr_type;
tree cached_lhs;
+ tree def;
bool insert = true;
bool assigns_var_p = false;
gimple stmt = gsi_stmt (*gsi);
- tree def = gimple_get_lhs (stmt);
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ def = gimple_phi_result (stmt);
+ else
+ def = gimple_get_lhs (stmt);
/* Certain expressions on the RHS can be optimized away, but can not
themselves be entered into the hash tables. */
}
else if (gimple_code (stmt) == GIMPLE_SWITCH)
expr_type = TREE_TYPE (gimple_switch_index (stmt));
+ else if (gimple_code (stmt) == GIMPLE_PHI)
+ /* We can't propagate into a phi, so the logic below doesn't apply.
+ Instead record an equivalence between the cached LHS and the
+ PHI result of this statement, provided they are in the same block.
+ This should be sufficient to kill the redundant phi. */
+ {
+ if (def && cached_lhs)
+ record_const_or_copy (def, cached_lhs);
+ return;
+ }
else
gcc_unreachable ();
|| useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
|| may_propagate_copy_into_stmt (stmt, cached_lhs))
{
-#if defined ENABLE_CHECKING
- gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
- || is_gimple_min_invariant (cached_lhs));
-#endif
+ gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
+ || is_gimple_min_invariant (cached_lhs));
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
opt_stats.num_re++;
-
+
if (assigns_var_p
&& !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
cached_lhs = fold_convert (expr_type, cached_lhs);
&& gimple_assign_single_p (stmt))
{
tree rhs = gimple_assign_rhs1 (stmt);
-
+
/* If the RHS of the assignment is a constant or another variable that
may be propagated, register it in the CONST_AND_COPIES table. We
do not need to record unwind data for this, since this is a true
val = SSA_NAME_VALUE (op);
if (val && val != op)
{
- /* Do not change the base variable in the virtual operand
- tables. That would make it impossible to reconstruct
- the renamed virtual operand if we later modify this
- statement. Also only allow the new value to be an SSA_NAME
- for propagation into virtual operands. */
- if (!is_gimple_reg (op)
- && (TREE_CODE (val) != SSA_NAME
- || is_gimple_reg (val)
- || get_virtual_var (val) != get_virtual_var (op)))
- return;
-
/* Do not replace hard register operands in asm statements. */
if (gimple_code (stmt) == GIMPLE_ASM
&& !may_propagate_copy_into_asm (op))
}
/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
- known value for that SSA_NAME (or NULL if no value is known).
+ known value for that SSA_NAME (or NULL if no value is known).
Propagate values from CONST_AND_COPIES into the uses, vuses and
vdef_ops of STMT. */
use_operand_p op_p;
ssa_op_iter iter;
- FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
- {
- if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
- cprop_operand (stmt, op_p);
- }
+ FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE)
+ cprop_operand (stmt, op_p);
}
/* Optimize the statement pointed to by iterator SI.
-
+
We try to perform some simplistic global redundancy elimination and
constant propagation:
bool modified_p = false;
old_stmt = stmt = gsi_stmt (si);
-
- if (gimple_code (stmt) == GIMPLE_COND)
- canonicalize_comparison (stmt);
-
- update_stmt_if_modified (stmt);
- opt_stats.num_stmts++;
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
+ if (gimple_code (stmt) == GIMPLE_COND)
+ canonicalize_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);
/* Check for redundant computations. Do this optimization only
for assignments that have no volatile ops and conditionals. */
- may_optimize_p = (!gimple_has_volatile_ops (stmt)
- && ((is_gimple_assign (stmt)
- && !gimple_rhs_has_side_effects (stmt))
+ may_optimize_p = (!gimple_has_side_effects (stmt)
+ && (is_gimple_assign (stmt)
|| (is_gimple_call (stmt)
- && gimple_call_lhs (stmt) != NULL_TREE
- && !gimple_rhs_has_side_effects (stmt))
+ && gimple_call_lhs (stmt) != NULL_TREE)
|| gimple_code (stmt) == GIMPLE_COND
|| gimple_code (stmt) == GIMPLE_SWITCH));
update_stmt_if_modified (stmt);
eliminate_redundant_computations (&si);
stmt = gsi_stmt (si);
+
+ /* Perform simple redundant store elimination. */
+ if (gimple_assign_single_p (stmt)
+ && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree cached_lhs;
+ gimple new_stmt;
+ if (TREE_CODE (rhs) == SSA_NAME)
+ {
+ tree tem = SSA_NAME_VALUE (rhs);
+ if (tem)
+ rhs = tem;
+ }
+ /* Build a new statement with the RHS and LHS exchanged. */
+ if (TREE_CODE (rhs) == SSA_NAME)
+ {
+ gimple defstmt = SSA_NAME_DEF_STMT (rhs);
+ new_stmt = gimple_build_assign (rhs, lhs);
+ SSA_NAME_DEF_STMT (rhs) = defstmt;
+ }
+ else
+ new_stmt = gimple_build_assign (rhs, lhs);
+ gimple_set_vuse (new_stmt, gimple_vuse (stmt));
+ cached_lhs = lookup_avail_expr (new_stmt, false);
+ if (cached_lhs
+ && rhs == cached_lhs)
+ {
+ basic_block bb = gimple_bb (stmt);
+ int lp_nr = lookup_stmt_eh_lp (stmt);
+ unlink_stmt_vdef (stmt);
+ gsi_remove (&si, true);
+ if (lp_nr != 0)
+ {
+ bitmap_set_bit (need_eh_cleanup, bb->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Flagged to clear EH edges.\n");
+ }
+ return;
+ }
+ }
}
/* Record any additional equivalences created by this statement. */
where it goes. If that is the case, then mark the CFG as altered.
This will cause us to later call remove_unreachable_blocks and
- cleanup_tree_cfg when it is safe to do so. It is not safe to
+ cleanup_tree_cfg when it is safe to do so. It is not safe to
clean things up here since removal of edges and such can trigger
the removal of PHI nodes, which in turn can release SSA_NAMEs to
the manager.
if (gimple_modified_p (stmt) || modified_p)
{
tree val = NULL;
-
+
update_stmt_if_modified (stmt);
if (gimple_code (stmt) == GIMPLE_COND)
void **slot;
tree lhs;
tree temp;
- struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
+ struct expr_hash_elt element;
- /* Get LHS of assignment or call, else NULL_TREE. */
- lhs = gimple_get_lhs (stmt);
+ /* Get LHS of phi, assignment, or call; else NULL_TREE. */
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ lhs = gimple_phi_result (stmt);
+ else
+ lhs = gimple_get_lhs (stmt);
- initialize_hash_element (stmt, lhs, element);
+ initialize_hash_element (stmt, lhs, &element);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "LKUP ");
- print_expr_hash_elt (dump_file, element);
+ print_expr_hash_elt (dump_file, &element);
}
/* Don't bother remembering constant assignments and copy operations.
Constants and copy operations are handled by the constant/copy propagator
in optimize_stmt. */
- if (element->expr.kind == EXPR_SINGLE
- && (TREE_CODE (element->expr.ops.single.rhs) == SSA_NAME
- || is_gimple_min_invariant (element->expr.ops.single.rhs)))
- {
- free (element);
- return NULL_TREE;
- }
+ if (element.expr.kind == EXPR_SINGLE
+ && (TREE_CODE (element.expr.ops.single.rhs) == SSA_NAME
+ || is_gimple_min_invariant (element.expr.ops.single.rhs)))
+ return NULL_TREE;
/* Finally try to find the expression in the main expression hash table. */
- slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
+ slot = htab_find_slot_with_hash (avail_exprs, &element, element.hash,
(insert ? INSERT : NO_INSERT));
if (slot == NULL)
- {
- free (element);
- return NULL_TREE;
- }
+ return NULL_TREE;
if (*slot == NULL)
{
- *slot = (void *) element;
+ struct expr_hash_elt *element2 = XNEW (struct expr_hash_elt);
+ *element2 = element;
+ element2->stamp = element2;
+ *slot = (void *) element2;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "2>>> ");
- print_expr_hash_elt (dump_file, element);
+ print_expr_hash_elt (dump_file, element2);
}
- VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
+ VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element2);
return NULL_TREE;
}
lhs = temp;
}
- free (element);
-
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "FIND: ");
if (arg == lhs)
continue;
+ else if (!arg)
+ break;
else if (!val)
val = arg;
- else if (!operand_equal_p (arg, val, 0))
+ else if (arg == val)
+ continue;
+ /* We bring in some of operand_equal_p not only to speed things
+ up, but also to avoid crashing when dereferencing the type of
+ a released SSA name. */
+ else if (TREE_CODE (val) != TREE_CODE (arg)
+ || TREE_CODE (val) == SSA_NAME
+ || !operand_equal_p (arg, val, 0))
break;
}
return (i == gimple_phi_num_args (phi) ? val : NULL);
nodes as well in an effort to pick up secondary optimization
opportunities. */
-static void
+static void
propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
{
/* First verify that propagation is valid and isn't going to move a
fprintf (dump_file, "'\n");
}
- /* Walk over every use of LHS and try to replace the use with RHS.
+ /* Walk over every use of LHS and try to replace the use with RHS.
At this point the only reason why such a propagation would not
be successful would be if the use occurs in an ASM_EXPR. */
FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
into debug stmts will occur then. */
if (gimple_debug_bind_p (use_stmt))
continue;
-
+
/* It's not always safe to propagate into an ASM_EXPR. */
if (gimple_code (use_stmt) == GIMPLE_ASM
&& ! may_propagate_copy_into_asm (lhs))
continue;
}
+ /* It's not ok to propagate into the definition stmt of RHS.
+ <bb 9>:
+ # prephitmp.12_36 = PHI <g_67.1_6(9)>
+ g_67.1_6 = prephitmp.12_36;
+ goto <bb 9>;
+ While this is strictly all dead code we do not want to
+ deal with this here. */
+ if (TREE_CODE (rhs) == SSA_NAME
+ && SSA_NAME_DEF_STMT (rhs) == use_stmt)
+ {
+ all = false;
+ continue;
+ }
+
/* Dump details. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
continue;
}
- /* From this point onward we are propagating into a
+ /* From this point onward we are propagating into a
real statement. Folding may (or may not) be possible,
we may expose new operands, expose dead EH edges,
etc. */
GIMPLE_ASSIGN, and there is no way to effect such a
transformation in-place. We might want to consider
using the more general fold_stmt here. */
- fold_stmt_inplace (use_stmt);
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
+ fold_stmt_inplace (&gsi);
+ }
/* Sometimes propagation can expose new operands to the
renamer. */
}
}
- /* Ensure there is nothing else to do. */
+ /* Ensure there is nothing else to do. */
gcc_assert (!all || has_zero_uses (lhs));
/* If we were able to propagate away all uses of LHS, then
A set bit indicates that the statement or PHI node which
defines the SSA_NAME should be (re)examined to determine if
it has become a degenerate PHI or trivial const/copy propagation
- opportunity.
+ opportunity.
Experiments have show we generally get better compilation
time behavior with bitmaps rather than sbitmaps. */
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_cleanup_cfg
- | TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
| TODO_verify_stmts
OSDN Git Service
