/* Value Numbering routines for tree expressions.
|
/* Value Numbering routines for tree expressions.
|
Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
|
Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
|
<stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
|
<stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify
|
GCC is free software; you can redistribute it and/or modify
|
it under the terms of the GNU General Public License as published by
|
it under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3, or (at your option)
|
the Free Software Foundation; either version 3, or (at your option)
|
any later version.
|
any later version.
|
|
|
GCC is distributed in the hope that it will be useful,
|
GCC is distributed in the hope that it will be useful,
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
GNU General Public License for more details.
|
GNU General Public License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "hashtab.h"
|
#include "hashtab.h"
|
#include "langhooks.h"
|
#include "langhooks.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
|
|
/* The value table that maps expressions to values. */
|
/* The value table that maps expressions to values. */
|
static htab_t value_table;
|
static htab_t value_table;
|
|
|
/* Map expressions to values. These are simple pairs of expressions
|
/* Map expressions to values. These are simple pairs of expressions
|
and the values they represent. To find the value represented by
|
and the values they represent. To find the value represented by
|
an expression, we use a hash table where the elements are {e,v}
|
an expression, we use a hash table where the elements are {e,v}
|
pairs, and the expression is the key. */
|
pairs, and the expression is the key. */
|
typedef struct val_expr_pair_d
|
typedef struct val_expr_pair_d
|
{
|
{
|
/* Value handle. */
|
/* Value handle. */
|
tree v;
|
tree v;
|
|
|
/* Associated expression. */
|
/* Associated expression. */
|
tree e;
|
tree e;
|
|
|
/* For comparing virtual uses in E. */
|
/* For comparing virtual uses in E. */
|
VEC (tree, gc) *vuses;
|
VEC (tree, gc) *vuses;
|
|
|
/* E's hash value. */
|
/* E's hash value. */
|
hashval_t hashcode;
|
hashval_t hashcode;
|
} *val_expr_pair_t;
|
} *val_expr_pair_t;
|
|
|
static void set_value_handle (tree e, tree v);
|
static void set_value_handle (tree e, tree v);
|
|
|
|
|
/* Create and return a new value handle node of type TYPE. */
|
/* Create and return a new value handle node of type TYPE. */
|
|
|
static tree
|
static tree
|
make_value_handle (tree type)
|
make_value_handle (tree type)
|
{
|
{
|
static unsigned int id = 0;
|
static unsigned int id = 0;
|
tree vh;
|
tree vh;
|
|
|
vh = build0 (VALUE_HANDLE, type);
|
vh = build0 (VALUE_HANDLE, type);
|
VALUE_HANDLE_ID (vh) = id++;
|
VALUE_HANDLE_ID (vh) = id++;
|
return vh;
|
return vh;
|
}
|
}
|
|
|
|
|
/* Given an expression EXPR, compute a hash value number using the
|
/* Given an expression EXPR, compute a hash value number using the
|
code of the expression, its real operands and virtual operands (if
|
code of the expression, its real operands and virtual operands (if
|
any).
|
any).
|
|
|
VAL can be used to iterate by passing previous value numbers (it is
|
VAL can be used to iterate by passing previous value numbers (it is
|
used by iterative_hash_expr). */
|
used by iterative_hash_expr). */
|
|
|
hashval_t
|
hashval_t
|
vn_compute (tree expr, hashval_t val)
|
vn_compute (tree expr, hashval_t val)
|
{
|
{
|
/* EXPR must not be a statement. We are only interested in value
|
/* EXPR must not be a statement. We are only interested in value
|
numbering expressions on the RHS of assignments. */
|
numbering expressions on the RHS of assignments. */
|
gcc_assert (expr);
|
gcc_assert (expr);
|
gcc_assert (!expr->common.ann
|
gcc_assert (!expr->common.ann
|
|| expr->common.ann->common.type != STMT_ANN);
|
|| expr->common.ann->common.type != STMT_ANN);
|
|
|
val = iterative_hash_expr (expr, val);
|
val = iterative_hash_expr (expr, val);
|
return val;
|
return val;
|
}
|
}
|
|
|
/* Compare two expressions E1 and E2 and return true if they are
|
/* Compare two expressions E1 and E2 and return true if they are
|
equal. */
|
equal. */
|
|
|
bool
|
bool
|
expressions_equal_p (tree e1, tree e2)
|
expressions_equal_p (tree e1, tree e2)
|
{
|
{
|
tree te1, te2;
|
tree te1, te2;
|
|
|
if (e1 == e2)
|
if (e1 == e2)
|
return true;
|
return true;
|
|
|
te1 = TREE_TYPE (e1);
|
te1 = TREE_TYPE (e1);
|
te2 = TREE_TYPE (e2);
|
te2 = TREE_TYPE (e2);
|
|
|
if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
|
if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
|
{
|
{
|
tree lop1 = e1;
|
tree lop1 = e1;
|
tree lop2 = e2;
|
tree lop2 = e2;
|
for (lop1 = e1, lop2 = e2;
|
for (lop1 = e1, lop2 = e2;
|
lop1 || lop2;
|
lop1 || lop2;
|
lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
|
lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
|
{
|
{
|
if (!lop1 || !lop2)
|
if (!lop1 || !lop2)
|
return false;
|
return false;
|
if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
|
if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
|
return false;
|
return false;
|
}
|
}
|
return true;
|
return true;
|
|
|
}
|
}
|
else if (TREE_CODE (e1) == TREE_CODE (e2)
|
else if (TREE_CODE (e1) == TREE_CODE (e2)
|
&& (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
|
&& (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
|
&& operand_equal_p (e1, e2, OEP_PURE_SAME))
|
&& operand_equal_p (e1, e2, OEP_PURE_SAME))
|
return true;
|
return true;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
|
|
/* Hash a {v,e} pair that is pointed to by P.
|
/* Hash a {v,e} pair that is pointed to by P.
|
The hashcode is cached in the val_expr_pair, so we just return
|
The hashcode is cached in the val_expr_pair, so we just return
|
that. */
|
that. */
|
|
|
static hashval_t
|
static hashval_t
|
val_expr_pair_hash (const void *p)
|
val_expr_pair_hash (const void *p)
|
{
|
{
|
const val_expr_pair_t ve = (val_expr_pair_t) p;
|
const val_expr_pair_t ve = (val_expr_pair_t) p;
|
return ve->hashcode;
|
return ve->hashcode;
|
}
|
}
|
|
|
|
|
/* Given two val_expr_pair_t's, return true if they represent the same
|
/* Given two val_expr_pair_t's, return true if they represent the same
|
expression, false otherwise.
|
expression, false otherwise.
|
P1 and P2 should point to the val_expr_pair_t's to be compared. */
|
P1 and P2 should point to the val_expr_pair_t's to be compared. */
|
|
|
static int
|
static int
|
val_expr_pair_expr_eq (const void *p1, const void *p2)
|
val_expr_pair_expr_eq (const void *p1, const void *p2)
|
{
|
{
|
int i;
|
int i;
|
tree vuse1;
|
tree vuse1;
|
const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
|
const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
|
const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
|
const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
|
|
|
if (! expressions_equal_p (ve1->e, ve2->e))
|
if (! expressions_equal_p (ve1->e, ve2->e))
|
return false;
|
return false;
|
|
|
if (ve1->vuses == ve2->vuses)
|
if (ve1->vuses == ve2->vuses)
|
return true;
|
return true;
|
|
|
if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
|
if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
|
return false;
|
return false;
|
|
|
for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
|
for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
|
{
|
{
|
if (VEC_index (tree, ve2->vuses, i) != vuse1)
|
if (VEC_index (tree, ve2->vuses, i) != vuse1)
|
return false;
|
return false;
|
}
|
}
|
return true;
|
return true;
|
}
|
}
|
|
|
|
|
/* Set the value handle for expression E to value V. */
|
/* Set the value handle for expression E to value V. */
|
|
|
static void
|
static void
|
set_value_handle (tree e, tree v)
|
set_value_handle (tree e, tree v)
|
{
|
{
|
if (TREE_CODE (e) == SSA_NAME)
|
if (TREE_CODE (e) == SSA_NAME)
|
SSA_NAME_VALUE (e) = v;
|
SSA_NAME_VALUE (e) = v;
|
else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
|
else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
|
|| TREE_CODE (e) == CONSTRUCTOR)
|
|| TREE_CODE (e) == CONSTRUCTOR)
|
get_tree_common_ann (e)->value_handle = v;
|
get_tree_common_ann (e)->value_handle = v;
|
else
|
else
|
/* Do nothing. Constants are their own value handles. */
|
/* Do nothing. Constants are their own value handles. */
|
gcc_assert (is_gimple_min_invariant (e));
|
gcc_assert (is_gimple_min_invariant (e));
|
}
|
}
|
|
|
/* Copy the virtual uses from STMT into a newly allocated VEC(tree),
|
/* Copy the virtual uses from STMT into a newly allocated VEC(tree),
|
and return the VEC(tree). */
|
and return the VEC(tree). */
|
|
|
static VEC (tree, gc) *
|
static VEC (tree, gc) *
|
copy_vuses_from_stmt (tree stmt)
|
copy_vuses_from_stmt (tree stmt)
|
{
|
{
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
tree vuse;
|
tree vuse;
|
VEC (tree, gc) *vuses = NULL;
|
VEC (tree, gc) *vuses = NULL;
|
|
|
if (!stmt)
|
if (!stmt)
|
return NULL;
|
return NULL;
|
|
|
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
|
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
|
VEC_safe_push (tree, gc, vuses, vuse);
|
VEC_safe_push (tree, gc, vuses, vuse);
|
|
|
return vuses;
|
return vuses;
|
}
|
}
|
|
|
/* Place for shared_vuses_from_stmt to shove vuses. */
|
/* Place for shared_vuses_from_stmt to shove vuses. */
|
static VEC (tree, gc) *shared_lookup_vuses;
|
static VEC (tree, gc) *shared_lookup_vuses;
|
|
|
/* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
|
/* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
|
This function will overwrite the current SHARED_LOOKUP_VUSES
|
This function will overwrite the current SHARED_LOOKUP_VUSES
|
variable. */
|
variable. */
|
|
|
static VEC (tree, gc) *
|
static VEC (tree, gc) *
|
shared_vuses_from_stmt (tree stmt)
|
shared_vuses_from_stmt (tree stmt)
|
{
|
{
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
tree vuse;
|
tree vuse;
|
|
|
if (!stmt)
|
if (!stmt)
|
return NULL;
|
return NULL;
|
|
|
VEC_truncate (tree, shared_lookup_vuses, 0);
|
VEC_truncate (tree, shared_lookup_vuses, 0);
|
|
|
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
|
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
|
VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
|
VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
|
|
|
if (VEC_length (tree, shared_lookup_vuses) > 1)
|
if (VEC_length (tree, shared_lookup_vuses) > 1)
|
sort_vuses (shared_lookup_vuses);
|
sort_vuses (shared_lookup_vuses);
|
|
|
return shared_lookup_vuses;
|
return shared_lookup_vuses;
|
}
|
}
|
|
|
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
|
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
|
EXPR to the value set for value VAL. */
|
EXPR to the value set for value VAL. */
|
|
|
void
|
void
|
vn_add (tree expr, tree val)
|
vn_add (tree expr, tree val)
|
{
|
{
|
vn_add_with_vuses (expr, val, NULL);
|
vn_add_with_vuses (expr, val, NULL);
|
}
|
}
|
|
|
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
|
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
|
EXPR to the value set for value VAL. VUSES represents the virtual
|
EXPR to the value set for value VAL. VUSES represents the virtual
|
use operands associated with EXPR. It is used when computing a
|
use operands associated with EXPR. It is used when computing a
|
hash value for EXPR. */
|
hash value for EXPR. */
|
|
|
void
|
void
|
vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
|
vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
|
{
|
{
|
void **slot;
|
void **slot;
|
val_expr_pair_t new_pair;
|
val_expr_pair_t new_pair;
|
|
|
new_pair = XNEW (struct val_expr_pair_d);
|
new_pair = XNEW (struct val_expr_pair_d);
|
new_pair->e = expr;
|
new_pair->e = expr;
|
new_pair->v = val;
|
new_pair->v = val;
|
new_pair->vuses = vuses;
|
new_pair->vuses = vuses;
|
new_pair->hashcode = vn_compute (expr, 0);
|
new_pair->hashcode = vn_compute (expr, 0);
|
slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
|
slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
|
INSERT);
|
INSERT);
|
if (*slot)
|
if (*slot)
|
free (*slot);
|
free (*slot);
|
*slot = (void *) new_pair;
|
*slot = (void *) new_pair;
|
|
|
set_value_handle (expr, val);
|
set_value_handle (expr, val);
|
if (TREE_CODE (val) == VALUE_HANDLE)
|
if (TREE_CODE (val) == VALUE_HANDLE)
|
add_to_value (val, expr);
|
add_to_value (val, expr);
|
}
|
}
|
|
|
|
|
/* Search in VALUE_TABLE for an existing instance of expression EXPR,
|
/* Search in VALUE_TABLE for an existing instance of expression EXPR,
|
and return its value, or NULL if none has been set. STMT
|
and return its value, or NULL if none has been set. STMT
|
represents the stmt associated with EXPR. It is used when computing the
|
represents the stmt associated with EXPR. It is used when computing the
|
hash value for EXPR. */
|
hash value for EXPR. */
|
|
|
tree
|
tree
|
vn_lookup (tree expr, tree stmt)
|
vn_lookup (tree expr, tree stmt)
|
{
|
{
|
return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
|
return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
|
}
|
}
|
|
|
/* Search in VALUE_TABLE for an existing instance of expression EXPR,
|
/* Search in VALUE_TABLE for an existing instance of expression EXPR,
|
and return its value, or NULL if none has been set. VUSES is the
|
and return its value, or NULL if none has been set. VUSES is the
|
list of virtual use operands associated with EXPR. It is used when
|
list of virtual use operands associated with EXPR. It is used when
|
computing the hash value for EXPR. */
|
computing the hash value for EXPR. */
|
|
|
tree
|
tree
|
vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
|
vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
|
{
|
{
|
void **slot;
|
void **slot;
|
struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
|
struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
|
|
|
/* Constants are their own value. */
|
/* Constants are their own value. */
|
if (is_gimple_min_invariant (expr))
|
if (is_gimple_min_invariant (expr))
|
return expr;
|
return expr;
|
|
|
vep.e = expr;
|
vep.e = expr;
|
vep.vuses = vuses;
|
vep.vuses = vuses;
|
vep.hashcode = vn_compute (expr, 0);
|
vep.hashcode = vn_compute (expr, 0);
|
slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
|
slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
|
if (!slot)
|
if (!slot)
|
return NULL_TREE;
|
return NULL_TREE;
|
else
|
else
|
return ((val_expr_pair_t) *slot)->v;
|
return ((val_expr_pair_t) *slot)->v;
|
}
|
}
|
|
|
|
|
/* A comparison function for use in qsort to compare vuses. Simply
|
/* A comparison function for use in qsort to compare vuses. Simply
|
subtracts version numbers. */
|
subtracts version numbers. */
|
|
|
static int
|
static int
|
vuses_compare (const void *pa, const void *pb)
|
vuses_compare (const void *pa, const void *pb)
|
{
|
{
|
const tree vusea = *((const tree *)pa);
|
const tree vusea = *((const tree *)pa);
|
const tree vuseb = *((const tree *)pb);
|
const tree vuseb = *((const tree *)pb);
|
int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
|
int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
|
|
|
return sn;
|
return sn;
|
}
|
}
|
|
|
/* Print out the "Created value <x> for <Y>" statement to the
|
/* Print out the "Created value <x> for <Y>" statement to the
|
dump_file.
|
dump_file.
|
This is factored because both versions of lookup use it, and it
|
This is factored because both versions of lookup use it, and it
|
obscures the real work going on in those functions. */
|
obscures the real work going on in those functions. */
|
|
|
static void
|
static void
|
print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
|
print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
|
{
|
{
|
fprintf (dump_file, "Created value ");
|
fprintf (dump_file, "Created value ");
|
print_generic_expr (dump_file, v, dump_flags);
|
print_generic_expr (dump_file, v, dump_flags);
|
fprintf (dump_file, " for ");
|
fprintf (dump_file, " for ");
|
print_generic_expr (dump_file, expr, dump_flags);
|
print_generic_expr (dump_file, expr, dump_flags);
|
|
|
if (vuses && VEC_length (tree, vuses) != 0)
|
if (vuses && VEC_length (tree, vuses) != 0)
|
{
|
{
|
size_t i;
|
size_t i;
|
tree vuse;
|
tree vuse;
|
|
|
fprintf (dump_file, " vuses: (");
|
fprintf (dump_file, " vuses: (");
|
for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
|
for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
|
{
|
{
|
print_generic_expr (dump_file, vuse, dump_flags);
|
print_generic_expr (dump_file, vuse, dump_flags);
|
if (VEC_length (tree, vuses) - 1 != i)
|
if (VEC_length (tree, vuses) - 1 != i)
|
fprintf (dump_file, ",");
|
fprintf (dump_file, ",");
|
}
|
}
|
fprintf (dump_file, ")");
|
fprintf (dump_file, ")");
|
}
|
}
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
/* Like vn_lookup, but creates a new value for expression EXPR, if
|
/* Like vn_lookup, but creates a new value for expression EXPR, if
|
EXPR doesn't already have a value. Return the existing/created
|
EXPR doesn't already have a value. Return the existing/created
|
value for EXPR. STMT represents the stmt associated with EXPR. It
|
value for EXPR. STMT represents the stmt associated with EXPR. It
|
is used when computing the VUSES for EXPR. */
|
is used when computing the VUSES for EXPR. */
|
|
|
tree
|
tree
|
vn_lookup_or_add (tree expr, tree stmt)
|
vn_lookup_or_add (tree expr, tree stmt)
|
{
|
{
|
tree v = vn_lookup (expr, stmt);
|
tree v = vn_lookup (expr, stmt);
|
if (v == NULL_TREE)
|
if (v == NULL_TREE)
|
{
|
{
|
VEC(tree,gc) *vuses;
|
VEC(tree,gc) *vuses;
|
|
|
v = make_value_handle (TREE_TYPE (expr));
|
v = make_value_handle (TREE_TYPE (expr));
|
vuses = copy_vuses_from_stmt (stmt);
|
vuses = copy_vuses_from_stmt (stmt);
|
sort_vuses (vuses);
|
sort_vuses (vuses);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
print_creation_to_file (v, expr, vuses);
|
print_creation_to_file (v, expr, vuses);
|
|
|
VALUE_HANDLE_VUSES (v) = vuses;
|
VALUE_HANDLE_VUSES (v) = vuses;
|
vn_add_with_vuses (expr, v, vuses);
|
vn_add_with_vuses (expr, v, vuses);
|
}
|
}
|
|
|
set_value_handle (expr, v);
|
set_value_handle (expr, v);
|
|
|
return v;
|
return v;
|
}
|
}
|
|
|
/* Sort the VUSE array so that we can do equality comparisons
|
/* Sort the VUSE array so that we can do equality comparisons
|
quicker on two vuse vecs. */
|
quicker on two vuse vecs. */
|
|
|
void
|
void
|
sort_vuses (VEC (tree,gc) *vuses)
|
sort_vuses (VEC (tree,gc) *vuses)
|
{
|
{
|
if (VEC_length (tree, vuses) > 1)
|
if (VEC_length (tree, vuses) > 1)
|
qsort (VEC_address (tree, vuses),
|
qsort (VEC_address (tree, vuses),
|
VEC_length (tree, vuses),
|
VEC_length (tree, vuses),
|
sizeof (tree),
|
sizeof (tree),
|
vuses_compare);
|
vuses_compare);
|
}
|
}
|
|
|
/* Like vn_lookup, but creates a new value for expression EXPR, if
|
/* Like vn_lookup, but creates a new value for expression EXPR, if
|
EXPR doesn't already have a value. Return the existing/created
|
EXPR doesn't already have a value. Return the existing/created
|
value for EXPR. STMT represents the stmt associated with EXPR. It is used
|
value for EXPR. STMT represents the stmt associated with EXPR. It is used
|
when computing the hash value for EXPR. */
|
when computing the hash value for EXPR. */
|
|
|
tree
|
tree
|
vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
|
vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
|
{
|
{
|
tree v = vn_lookup_with_vuses (expr, vuses);
|
tree v = vn_lookup_with_vuses (expr, vuses);
|
if (v == NULL_TREE)
|
if (v == NULL_TREE)
|
{
|
{
|
v = make_value_handle (TREE_TYPE (expr));
|
v = make_value_handle (TREE_TYPE (expr));
|
sort_vuses (vuses);
|
sort_vuses (vuses);
|
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
print_creation_to_file (v, expr, vuses);
|
print_creation_to_file (v, expr, vuses);
|
|
|
VALUE_HANDLE_VUSES (v) = vuses;
|
VALUE_HANDLE_VUSES (v) = vuses;
|
vn_add_with_vuses (expr, v, vuses);
|
vn_add_with_vuses (expr, v, vuses);
|
}
|
}
|
|
|
set_value_handle (expr, v);
|
set_value_handle (expr, v);
|
|
|
return v;
|
return v;
|
}
|
}
|
|
|
|
|
|
|
/* Get the value handle of EXPR. This is the only correct way to get
|
/* Get the value handle of EXPR. This is the only correct way to get
|
the value handle for a "thing". If EXPR does not have a value
|
the value handle for a "thing". If EXPR does not have a value
|
handle associated, it returns NULL_TREE.
|
handle associated, it returns NULL_TREE.
|
NB: If EXPR is min_invariant, this function is *required* to return EXPR. */
|
NB: If EXPR is min_invariant, this function is *required* to return EXPR. */
|
|
|
tree
|
tree
|
get_value_handle (tree expr)
|
get_value_handle (tree expr)
|
{
|
{
|
|
|
if (is_gimple_min_invariant (expr))
|
if (is_gimple_min_invariant (expr))
|
return expr;
|
return expr;
|
|
|
if (TREE_CODE (expr) == SSA_NAME)
|
if (TREE_CODE (expr) == SSA_NAME)
|
return SSA_NAME_VALUE (expr);
|
return SSA_NAME_VALUE (expr);
|
else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
|
else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
|
|| TREE_CODE (expr) == CONSTRUCTOR)
|
|| TREE_CODE (expr) == CONSTRUCTOR)
|
{
|
{
|
tree_ann_common_t ann = tree_common_ann (expr);
|
tree_ann_common_t ann = tree_common_ann (expr);
|
return ((ann) ? ann->value_handle : NULL_TREE);
|
return ((ann) ? ann->value_handle : NULL_TREE);
|
}
|
}
|
else
|
else
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
|
|
|
|
/* Initialize data structures used in value numbering. */
|
/* Initialize data structures used in value numbering. */
|
|
|
void
|
void
|
vn_init (void)
|
vn_init (void)
|
{
|
{
|
value_table = htab_create (511, val_expr_pair_hash,
|
value_table = htab_create (511, val_expr_pair_hash,
|
val_expr_pair_expr_eq, free);
|
val_expr_pair_expr_eq, free);
|
shared_lookup_vuses = NULL;
|
shared_lookup_vuses = NULL;
|
}
|
}
|
|
|
|
|
/* Delete data used for value numbering. */
|
/* Delete data used for value numbering. */
|
|
|
void
|
void
|
vn_delete (void)
|
vn_delete (void)
|
{
|
{
|
htab_delete (value_table);
|
htab_delete (value_table);
|
VEC_free (tree, gc, shared_lookup_vuses);
|
VEC_free (tree, gc, shared_lookup_vuses);
|
value_table = NULL;
|
value_table = NULL;
|
}
|
}
|
|
|
