/* SCC value numbering for trees
- Copyright (C) 2006, 2007, 2008, 2009
+ Copyright (C) 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org>
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "ggc.h"
#include "tree.h"
#include "basic-block.h"
#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "tree-inline.h"
#include "tree-flow.h"
#include "gimple.h"
#include "fibheap.h"
#include "hashtab.h"
#include "tree-iterator.h"
-#include "real.h"
#include "alloc-pool.h"
#include "tree-pass.h"
#include "flags.h"
get_or_alloc_constant_value_id (tree constant)
{
void **slot;
- vn_constant_t vc = XNEW (struct vn_constant_s);
+ struct vn_constant_s vc;
+ vn_constant_t vcp;
- vc->hashcode = vn_hash_constant_with_type (constant);
- vc->constant = constant;
- slot = htab_find_slot_with_hash (constant_to_value_id, vc,
- vc->hashcode, INSERT);
+ vc.hashcode = vn_hash_constant_with_type (constant);
+ vc.constant = constant;
+ slot = htab_find_slot_with_hash (constant_to_value_id, &vc,
+ vc.hashcode, INSERT);
if (*slot)
- {
- free (vc);
- return ((vn_constant_t)*slot)->value_id;
- }
- vc->value_id = get_next_value_id ();
- *slot = vc;
- bitmap_set_bit (constant_value_ids, vc->value_id);
- return vc->value_id;
+ return ((vn_constant_t)*slot)->value_id;
+
+ vcp = XNEW (struct vn_constant_s);
+ vcp->hashcode = vc.hashcode;
+ vcp->constant = constant;
+ vcp->value_id = get_next_value_id ();
+ *slot = (void *) vcp;
+ bitmap_set_bit (constant_value_ids, vcp->value_id);
+ return vcp->value_id;
}
/* Return true if V is a value id for a constant. */
/* Compute the hash for a reference operand VRO1. */
static hashval_t
-vn_reference_op_compute_hash (const vn_reference_op_t vro1)
+vn_reference_op_compute_hash (const vn_reference_op_t vro1, hashval_t result)
{
- hashval_t result = 0;
+ result = iterative_hash_hashval_t (vro1->opcode, result);
if (vro1->op0)
- result += iterative_hash_expr (vro1->op0, vro1->opcode);
+ result = iterative_hash_expr (vro1->op0, result);
if (vro1->op1)
- result += iterative_hash_expr (vro1->op1, vro1->opcode);
+ result = iterative_hash_expr (vro1->op1, result);
if (vro1->op2)
- result += iterative_hash_expr (vro1->op2, vro1->opcode);
+ result = iterative_hash_expr (vro1->op2, result);
return result;
}
hashval_t
vn_reference_compute_hash (const vn_reference_t vr1)
{
- hashval_t result;
+ hashval_t result = 0;
int i;
vn_reference_op_t vro;
- result = iterative_hash_expr (vr1->vuse, 0);
for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
- result += vn_reference_op_compute_hash (vro);
+ result = vn_reference_op_compute_hash (vro, result);
+ if (vr1->vuse)
+ result += SSA_NAME_VERSION (vr1->vuse);
return result;
}
*i_p = i;
}
+/* Optimize the reference REF to a constant if possible or return
+ NULL_TREE if not. */
+
+tree
+fully_constant_vn_reference_p (vn_reference_t ref)
+{
+ VEC (vn_reference_op_s, heap) *operands = ref->operands;
+ vn_reference_op_t op;
+
+ /* Try to simplify the translated expression if it is
+ a call to a builtin function with at most two arguments. */
+ op = VEC_index (vn_reference_op_s, operands, 0);
+ if (op->opcode == CALL_EXPR
+ && TREE_CODE (op->op0) == ADDR_EXPR
+ && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL
+ && DECL_BUILT_IN (TREE_OPERAND (op->op0, 0))
+ && VEC_length (vn_reference_op_s, operands) >= 2
+ && VEC_length (vn_reference_op_s, operands) <= 3)
+ {
+ vn_reference_op_t arg0, arg1 = NULL;
+ bool anyconst = false;
+ arg0 = VEC_index (vn_reference_op_s, operands, 1);
+ if (VEC_length (vn_reference_op_s, operands) > 2)
+ arg1 = VEC_index (vn_reference_op_s, operands, 2);
+ if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant
+ || (arg0->opcode == ADDR_EXPR
+ && is_gimple_min_invariant (arg0->op0)))
+ anyconst = true;
+ if (arg1
+ && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant
+ || (arg1->opcode == ADDR_EXPR
+ && is_gimple_min_invariant (arg1->op0))))
+ anyconst = true;
+ if (anyconst)
+ {
+ tree folded = build_call_expr (TREE_OPERAND (op->op0, 0),
+ arg1 ? 2 : 1,
+ arg0->op0,
+ arg1 ? arg1->op0 : NULL);
+ if (folded
+ && TREE_CODE (folded) == NOP_EXPR)
+ folded = TREE_OPERAND (folded, 0);
+ if (folded
+ && is_gimple_min_invariant (folded))
+ return folded;
+ }
+ }
+
+ /* Simplify reads from constant strings. */
+ else if (op->opcode == ARRAY_REF
+ && TREE_CODE (op->op0) == INTEGER_CST
+ && integer_zerop (op->op1)
+ && VEC_length (vn_reference_op_s, operands) == 2)
+ {
+ vn_reference_op_t arg0;
+ arg0 = VEC_index (vn_reference_op_s, operands, 1);
+ if (arg0->opcode == STRING_CST
+ && (TYPE_MODE (op->type)
+ == TYPE_MODE (TREE_TYPE (TREE_TYPE (arg0->op0))))
+ && GET_MODE_CLASS (TYPE_MODE (op->type)) == MODE_INT
+ && GET_MODE_SIZE (TYPE_MODE (op->type)) == 1
+ && compare_tree_int (op->op0, TREE_STRING_LENGTH (arg0->op0)) < 0)
+ return build_int_cst_type (op->type,
+ (TREE_STRING_POINTER (arg0->op0)
+ [TREE_INT_CST_LOW (op->op0)]));
+ }
+
+ return NULL_TREE;
+}
+
/* Transform any SSA_NAME's in a vector of vn_reference_op_s
structures into their value numbers. This is done in-place, and
the vector passed in is returned. */
return NULL_TREE;
}
+static tree *last_vuse_ptr;
+
/* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_
with the current VUSE and performs the expression lookup. */
void **slot;
hashval_t hash;
+ if (last_vuse_ptr)
+ *last_vuse_ptr = vuse;
+
/* Fixup vuse and hash. */
- vr->hashcode = vr->hashcode - iterative_hash_expr (vr->vuse, 0);
+ if (vr->vuse)
+ vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse);
vr->vuse = SSA_VAL (vuse);
- vr->hashcode = vr->hashcode + iterative_hash_expr (vr->vuse, 0);
+ if (vr->vuse)
+ vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
hash = vr->hashcode;
slot = htab_find_slot_with_hash (current_info->references, vr,
return (void *)-1;
*ref = r;
+ /* Do not update last seen VUSE after translating. */
+ last_vuse_ptr = NULL;
+
/* Keep looking for the adjusted *REF / VR pair. */
return NULL;
}
{
struct vn_reference_s vr1;
vn_reference_t tmp;
+ tree cst;
if (!vnresult)
vnresult = &tmp;
vr1.type = type;
vr1.set = set;
vr1.hashcode = vn_reference_compute_hash (&vr1);
- vn_reference_lookup_1 (&vr1, vnresult);
+ if ((cst = fully_constant_vn_reference_p (&vr1)))
+ return cst;
+ vn_reference_lookup_1 (&vr1, vnresult);
if (!*vnresult
&& maywalk
&& vr1.vuse)
{
VEC (vn_reference_op_s, heap) *operands;
struct vn_reference_s vr1;
+ tree cst;
if (vnresult)
*vnresult = NULL;
vr1.type = TREE_TYPE (op);
vr1.set = get_alias_set (op);
vr1.hashcode = vn_reference_compute_hash (&vr1);
+ if ((cst = fully_constant_vn_reference_p (&vr1)))
+ return cst;
if (maywalk
&& vr1.vuse)
hashval_t
vn_nary_op_compute_hash (const vn_nary_op_t vno1)
{
- hashval_t hash = 0;
+ hashval_t hash;
unsigned i;
for (i = 0; i < vno1->length; ++i)
vno1->op[1] = temp;
}
+ hash = iterative_hash_hashval_t (vno1->opcode, 0);
for (i = 0; i < vno1->length; ++i)
- hash += iterative_hash_expr (vno1->op[i], vno1->opcode);
+ hash = iterative_hash_expr (vno1->op[i], hash);
return hash;
}
static inline hashval_t
vn_phi_compute_hash (vn_phi_t vp1)
{
- hashval_t result = 0;
+ hashval_t result;
int i;
tree phi1op;
tree type;
{
if (phi1op == VN_TOP)
continue;
- result += iterative_hash_expr (phi1op, result);
+ result = iterative_hash_expr (phi1op, result);
}
return result;
visit_reference_op_load (tree lhs, tree op, gimple stmt)
{
bool changed = false;
- tree result = vn_reference_lookup (op, gimple_vuse (stmt), true, NULL);
+ tree last_vuse;
+ tree result;
+
+ last_vuse = gimple_vuse (stmt);
+ last_vuse_ptr = &last_vuse;
+ result = vn_reference_lookup (op, gimple_vuse (stmt), true, NULL);
+ last_vuse_ptr = NULL;
/* If we have a VCE, try looking up its operand as it might be stored in
a different type. */
else
{
changed = set_ssa_val_to (lhs, lhs);
- vn_reference_insert (op, lhs, gimple_vuse (stmt));
+ vn_reference_insert (op, lhs, last_vuse);
}
return changed;
if (!e1 || !e2)
return false;
- /* Recurse on elements of lists. */
- if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
- {
- tree lop1 = e1;
- tree lop2 = e2;
- for (lop1 = e1, lop2 = e2;
- lop1 || lop2;
- lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
- {
- if (!lop1 || !lop2)
- return false;
- if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
- return false;
- }
- return true;
- }
-
/* Now perform the actual comparison. */
if (TREE_CODE (e1) == TREE_CODE (e2)
&& operand_equal_p (e1, e2, OEP_PURE_SAME))
vn_nary_may_trap (vn_nary_op_t nary)
{
tree type;
- tree rhs2;
+ tree rhs2 = NULL_TREE;
bool honor_nans = false;
bool honor_snans = false;
bool fp_operation = false;
&& TYPE_OVERFLOW_TRAPS (type))
honor_trapv = true;
}
- rhs2 = nary->op[1];
+ if (nary->length >= 2)
+ rhs2 = nary->op[1];
ret = operation_could_trap_helper_p (nary->opcode, fp_operation,
honor_trapv,
honor_nans, honor_snans, rhs2,