#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "tree-flow.h"
#include "hashtab.h"
#include "langhooks.h"
#include "tree-pass.h"
#include "tree-dump.h"
#include "diagnostic.h"
static htab_t value_table;
typedef struct val_expr_pair_d
{
tree v;
tree e;
VEC (tree, gc) *vuses;
hashval_t hashcode;
} *val_expr_pair_t;
static void set_value_handle (tree e, tree v);
static tree
make_value_handle (tree type)
{
static unsigned int id = 0;
tree vh;
vh = build0 (VALUE_HANDLE, type);
VALUE_HANDLE_ID (vh) = id++;
return vh;
}
hashval_t
vn_compute (tree expr, hashval_t val)
{
gcc_assert (expr);
gcc_assert (!expr->common.ann
|| expr->common.ann->common.type != STMT_ANN);
val = iterative_hash_expr (expr, val);
return val;
}
bool
expressions_equal_p (tree e1, tree e2)
{
tree te1, te2;
if (e1 == e2)
return true;
te1 = TREE_TYPE (e1);
te2 = TREE_TYPE (e2);
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;
}
else if (TREE_CODE (e1) == TREE_CODE (e2)
&& (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
&& operand_equal_p (e1, e2, OEP_PURE_SAME))
return true;
return false;
}
static hashval_t
val_expr_pair_hash (const void *p)
{
const val_expr_pair_t ve = (val_expr_pair_t) p;
return ve->hashcode;
}
static int
val_expr_pair_expr_eq (const void *p1, const void *p2)
{
int i;
tree vuse1;
const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
if (! expressions_equal_p (ve1->e, ve2->e))
return false;
if (ve1->vuses == ve2->vuses)
return true;
if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
return false;
for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
{
if (VEC_index (tree, ve2->vuses, i) != vuse1)
return false;
}
return true;
}
static void
set_value_handle (tree e, tree v)
{
if (TREE_CODE (e) == SSA_NAME)
SSA_NAME_VALUE (e) = v;
else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
|| TREE_CODE (e) == CONSTRUCTOR)
get_tree_common_ann (e)->value_handle = v;
else
gcc_assert (is_gimple_min_invariant (e));
}
static VEC (tree, gc) *
copy_vuses_from_stmt (tree stmt)
{
ssa_op_iter iter;
tree vuse;
VEC (tree, gc) *vuses = NULL;
if (!stmt)
return NULL;
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
VEC_safe_push (tree, gc, vuses, vuse);
return vuses;
}
static VEC (tree, gc) *shared_lookup_vuses;
static VEC (tree, gc) *
shared_vuses_from_stmt (tree stmt)
{
ssa_op_iter iter;
tree vuse;
if (!stmt)
return NULL;
VEC_truncate (tree, shared_lookup_vuses, 0);
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
if (VEC_length (tree, shared_lookup_vuses) > 1)
sort_vuses (shared_lookup_vuses);
return shared_lookup_vuses;
}
void
vn_add (tree expr, tree val)
{
vn_add_with_vuses (expr, val, NULL);
}
void
vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
{
void **slot;
val_expr_pair_t new_pair;
new_pair = XNEW (struct val_expr_pair_d);
new_pair->e = expr;
new_pair->v = val;
new_pair->vuses = vuses;
new_pair->hashcode = vn_compute (expr, 0);
slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
INSERT);
if (*slot)
free (*slot);
*slot = (void *) new_pair;
set_value_handle (expr, val);
if (TREE_CODE (val) == VALUE_HANDLE)
add_to_value (val, expr);
}
tree
vn_lookup (tree expr, tree stmt)
{
return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
}
tree
vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
{
void **slot;
struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
if (is_gimple_min_invariant (expr))
return expr;
vep.e = expr;
vep.vuses = vuses;
vep.hashcode = vn_compute (expr, 0);
slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
if (!slot)
return NULL_TREE;
else
return ((val_expr_pair_t) *slot)->v;
}
static int
vuses_compare (const void *pa, const void *pb)
{
const tree vusea = *((const tree *)pa);
const tree vuseb = *((const tree *)pb);
int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
return sn;
}
static void
print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
{
fprintf (dump_file, "Created value ");
print_generic_expr (dump_file, v, dump_flags);
fprintf (dump_file, " for ");
print_generic_expr (dump_file, expr, dump_flags);
if (vuses && VEC_length (tree, vuses) != 0)
{
size_t i;
tree vuse;
fprintf (dump_file, " vuses: (");
for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
{
print_generic_expr (dump_file, vuse, dump_flags);
if (VEC_length (tree, vuses) - 1 != i)
fprintf (dump_file, ",");
}
fprintf (dump_file, ")");
}
fprintf (dump_file, "\n");
}
tree
vn_lookup_or_add (tree expr, tree stmt)
{
tree v = vn_lookup (expr, stmt);
if (v == NULL_TREE)
{
VEC(tree,gc) *vuses;
v = make_value_handle (TREE_TYPE (expr));
vuses = copy_vuses_from_stmt (stmt);
sort_vuses (vuses);
if (dump_file && (dump_flags & TDF_DETAILS))
print_creation_to_file (v, expr, vuses);
VALUE_HANDLE_VUSES (v) = vuses;
vn_add_with_vuses (expr, v, vuses);
}
set_value_handle (expr, v);
return v;
}
void
sort_vuses (VEC (tree,gc) *vuses)
{
if (VEC_length (tree, vuses) > 1)
qsort (VEC_address (tree, vuses),
VEC_length (tree, vuses),
sizeof (tree),
vuses_compare);
}
tree
vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
{
tree v = vn_lookup_with_vuses (expr, vuses);
if (v == NULL_TREE)
{
v = make_value_handle (TREE_TYPE (expr));
sort_vuses (vuses);
if (dump_file && (dump_flags & TDF_DETAILS))
print_creation_to_file (v, expr, vuses);
VALUE_HANDLE_VUSES (v) = vuses;
vn_add_with_vuses (expr, v, vuses);
}
set_value_handle (expr, v);
return v;
}
tree
get_value_handle (tree expr)
{
if (is_gimple_min_invariant (expr))
return expr;
if (TREE_CODE (expr) == SSA_NAME)
return SSA_NAME_VALUE (expr);
else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
|| TREE_CODE (expr) == CONSTRUCTOR)
{
tree_ann_common_t ann = tree_common_ann (expr);
return ((ann) ? ann->value_handle : NULL_TREE);
}
else
gcc_unreachable ();
}
void
vn_init (void)
{
value_table = htab_create (511, val_expr_pair_hash,
val_expr_pair_expr_eq, free);
shared_lookup_vuses = NULL;
}
void
vn_delete (void)
{
htab_delete (value_table);
VEC_free (tree, gc, shared_lookup_vuses);
value_table = NULL;
}