#include "stor-layout.h"
#include "flags.h"
#include "tm_p.h"
+#include "predict.h"
+#include "vec.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "hard-reg-set.h"
+#include "input.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
#include "basic-block.h"
#include "cfgloop.h"
-#include "function.h"
+#include "inchash.h"
#include "gimple-pretty-print.h"
#include "tree-ssa-alias.h"
#include "internal-fn.h"
#include "params.h"
#include "tree-ssa-threadedge.h"
#include "tree-ssa-dom.h"
+#include "inchash.h"
/* This file implements optimizations on the dominator tree. */
struct expr_elt_hasher
{
- typedef expr_hash_elt value_type;
- typedef expr_hash_elt compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
- static inline void remove (value_type *);
+ typedef expr_hash_elt *value_type;
+ typedef expr_hash_elt *compare_type;
+ typedef int store_values_directly;
+ static inline hashval_t hash (const value_type &);
+ static inline bool equal (const value_type &, const compare_type &);
+ static inline void remove (value_type &);
};
inline hashval_t
-expr_elt_hasher::hash (const value_type *p)
+expr_elt_hasher::hash (const value_type &p)
{
return p->hash;
}
inline bool
-expr_elt_hasher::equal (const value_type *p1, const compare_type *p2)
+expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
{
gimple stmt1 = p1->stmt;
const struct hashable_expr *expr1 = &p1->expr;
/* Delete an expr_hash_elt and reclaim its storage. */
inline void
-expr_elt_hasher::remove (value_type *element)
+expr_elt_hasher::remove (value_type &element)
{
free_expr_hash_elt (element);
}
case GIMPLE_UNARY_RHS:
expr->kind = EXPR_UNARY;
expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
+ if (CONVERT_EXPR_CODE_P (subcode))
+ subcode = NOP_EXPR;
expr->ops.unary.op = subcode;
expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
break;
}
/* Generate a hash value for a pair of expressions. This can be used
- iteratively by passing a previous result as the VAL argument.
+ iteratively by passing a previous result in HSTATE.
The same hash value is always returned for a given pair of expressions,
regardless of the order in which they are presented. This is useful in
hashing the operands of commutative functions. */
-static hashval_t
-iterative_hash_exprs_commutative (const_tree t1,
- const_tree t2, hashval_t val)
+namespace inchash
{
- hashval_t one = iterative_hash_expr (t1, 0);
- hashval_t two = iterative_hash_expr (t2, 0);
- hashval_t t;
- if (one > two)
- t = one, one = two, two = t;
- val = iterative_hash_hashval_t (one, val);
- val = iterative_hash_hashval_t (two, val);
+static void
+add_expr_commutative (const_tree t1, const_tree t2, hash &hstate)
+{
+ hash one, two;
- return val;
+ inchash::add_expr (t1, one);
+ inchash::add_expr (t2, two);
+ hstate.add_commutative (one, two);
}
/* Compute a hash value for a hashable_expr value EXPR and a
previously accumulated hash value VAL. If two hashable_expr
values compare equal with hashable_expr_equal_p, they must
hash to the same value, given an identical value of VAL.
- The logic is intended to follow iterative_hash_expr in tree.c. */
+ The logic is intended to follow inchash::add_expr in tree.c. */
-static hashval_t
-iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val)
+static void
+add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
{
switch (expr->kind)
{
case EXPR_SINGLE:
- val = iterative_hash_expr (expr->ops.single.rhs, val);
+ inchash::add_expr (expr->ops.single.rhs, hstate);
break;
case EXPR_UNARY:
- val = iterative_hash_object (expr->ops.unary.op, val);
+ hstate.add_object (expr->ops.unary.op);
/* Make sure to include signedness in the hash computation.
Don't hash the type, that can lead to having nodes which
have different hash codes. */
if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
|| expr->ops.unary.op == NON_LVALUE_EXPR)
- val += TYPE_UNSIGNED (expr->type);
+ hstate.add_int (TYPE_UNSIGNED (expr->type));
- val = iterative_hash_expr (expr->ops.unary.opnd, val);
+ inchash::add_expr (expr->ops.unary.opnd, hstate);
break;
case EXPR_BINARY:
- val = iterative_hash_object (expr->ops.binary.op, val);
+ hstate.add_object (expr->ops.binary.op);
if (commutative_tree_code (expr->ops.binary.op))
- val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
- expr->ops.binary.opnd1, val);
+ inchash::add_expr_commutative (expr->ops.binary.opnd0,
+ expr->ops.binary.opnd1, hstate);
else
{
- val = iterative_hash_expr (expr->ops.binary.opnd0, val);
- val = iterative_hash_expr (expr->ops.binary.opnd1, val);
+ inchash::add_expr (expr->ops.binary.opnd0, hstate);
+ inchash::add_expr (expr->ops.binary.opnd1, hstate);
}
break;
case EXPR_TERNARY:
- val = iterative_hash_object (expr->ops.ternary.op, val);
+ hstate.add_object (expr->ops.ternary.op);
if (commutative_ternary_tree_code (expr->ops.ternary.op))
- val = iterative_hash_exprs_commutative (expr->ops.ternary.opnd0,
- expr->ops.ternary.opnd1, val);
+ inchash::add_expr_commutative (expr->ops.ternary.opnd0,
+ expr->ops.ternary.opnd1, hstate);
else
{
- val = iterative_hash_expr (expr->ops.ternary.opnd0, val);
- val = iterative_hash_expr (expr->ops.ternary.opnd1, val);
+ inchash::add_expr (expr->ops.ternary.opnd0, hstate);
+ inchash::add_expr (expr->ops.ternary.opnd1, hstate);
}
- val = iterative_hash_expr (expr->ops.ternary.opnd2, val);
+ inchash::add_expr (expr->ops.ternary.opnd2, hstate);
break;
case EXPR_CALL:
enum tree_code code = CALL_EXPR;
gimple fn_from;
- val = iterative_hash_object (code, val);
+ hstate.add_object (code);
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);
+ hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from));
else
- val = iterative_hash_expr (gimple_call_fn (fn_from), val);
+ inchash::add_expr (gimple_call_fn (fn_from), hstate);
for (i = 0; i < expr->ops.call.nargs; i++)
- val = iterative_hash_expr (expr->ops.call.args[i], val);
+ inchash::add_expr (expr->ops.call.args[i], hstate);
}
break;
size_t i;
for (i = 0; i < expr->ops.phi.nargs; i++)
- val = iterative_hash_expr (expr->ops.phi.args[i], val);
+ inchash::add_expr (expr->ops.phi.args[i], hstate);
}
break;
default:
gcc_unreachable ();
}
+}
- return val;
}
/* Print a diagnostic dump of an expression hash table entry. */
GIMPLE_PASS, /* type */
"dom", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_execute */
TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
( PROP_cfg | PROP_ssa ), /* properties_required */
0, /* properties_provided */
this, since this is a true assignment and not an equivalence
inferred from a comparison. All uses of this ssa name are dominated
by this assignment, so unwinding just costs time and space. */
- if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
+ if (i == gimple_phi_num_args (phi)
+ && may_propagate_copy (lhs, rhs))
set_ssa_name_value (lhs, rhs);
}
}
const_and_copies_stack.quick_push (x);
}
+/* Record that X is equal to Y in const_and_copies. Record undo
+ information in the block-local vector. */
+
+static void
+record_const_or_copy (tree x, tree y)
+{
+ tree prev_x = SSA_NAME_VALUE (x);
+
+ gcc_assert (TREE_CODE (x) == SSA_NAME);
+
+ if (TREE_CODE (y) == SSA_NAME)
+ {
+ tree tmp = SSA_NAME_VALUE (y);
+ if (tmp)
+ y = tmp;
+ }
+
+ record_const_or_copy_1 (x, y, prev_x);
+}
+
/* Return the loop depth of the basic block of the defining statement of X.
This number should not be treated as absolutely correct because the loop
information may not be completely up-to-date when dom runs. However, it
will be relatively correct, and as more passes are taught to keep loop info
up to date, the result will become more and more accurate. */
-int
+static int
loop_depth_of_name (tree x)
{
gimple defstmt;
return bb_loop_depth (defbb);
}
-/* Record that X is equal to Y in const_and_copies. Record undo
- information in the block-local vector. */
-
-static void
-record_const_or_copy (tree x, tree y)
-{
- tree prev_x = SSA_NAME_VALUE (x);
-
- gcc_assert (TREE_CODE (x) == SSA_NAME);
-
- if (TREE_CODE (y) == SSA_NAME)
- {
- tree tmp = SSA_NAME_VALUE (y);
- if (tmp)
- y = tmp;
- }
-
- record_const_or_copy_1 (x, y, prev_x);
-}
-
/* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
This constrains the cases in which we may treat this as assignment. */
if (is_gimple_min_invariant (y))
;
else if (is_gimple_min_invariant (x)
+ /* ??? When threading over backedges the following is important
+ for correctness. See PR61757. */
|| (loop_depth_of_name (x) <= loop_depth_of_name (y)))
prev_x = x, x = y, y = prev_x, prev_x = prev_y;
else if (prev_x && is_gimple_min_invariant (prev_x))
if (!may_propagate_copy (op, val))
return;
- /* Do not propagate addresses that point to volatiles into memory
- stmts without volatile operands. */
- if (POINTER_TYPE_P (TREE_TYPE (val))
- && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val)))
- && gimple_has_mem_ops (stmt)
- && !gimple_has_volatile_ops (stmt))
- return;
-
- /* Do not propagate copies if the propagated value is at a deeper loop
- depth than the propagatee. Otherwise, this may move loop variant
- variables outside of their loops and prevent coalescing
- opportunities. If the value was loop invariant, it will be hoisted
- by LICM and exposed for copy propagation. */
- if (loop_depth_of_name (val) > loop_depth_of_name (op))
- return;
-
/* Do not propagate copies into simple IV increment statements.
See PR23821 for how this can disturb IV analysis. */
if (TREE_CODE (val) != INTEGER_CST
gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
tree vuse;
- hashval_t val = 0;
+ inchash::hash hstate;
- val = iterative_hash_hashable_expr (expr, val);
+ inchash::add_hashable_expr (expr, hstate);
/* If the hash table entry is not associated with a statement, then we
can just hash the expression and not worry about virtual operands
and such. */
if (!stmt)
- return val;
+ return hstate.end ();
/* Add the SSA version numbers of the vuse operand. This is important
because compound variables like arrays are not renamed in the
operands. Rather, the rename is done on the virtual variable
representing all the elements of the array. */
if ((vuse = gimple_vuse (stmt)))
- val = iterative_hash_expr (vuse, val);
+ inchash::add_expr (vuse, hstate);
- return val;
+ return hstate.end ();
}
/* PHI-ONLY copy and constant propagation. This pass is meant to clean
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
- loop variant variable outside its loop. */
- if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
- && (TREE_CODE (rhs) != SSA_NAME
- || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
- && may_propagate_copy (lhs, rhs)
- && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
+ /* First verify that propagation is valid. */
+ if (may_propagate_copy (lhs, rhs))
{
use_operand_p use_p;
imm_use_iterator iter;
GIMPLE_PASS, /* type */
"phicprop", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_execute */
TV_TREE_PHI_CPROP, /* tv_id */
( PROP_cfg | PROP_ssa ), /* properties_required */
0, /* properties_provided */