/* SCC value numbering for trees
- Copyright (C) 2006
+ Copyright (C) 2006, 2007
Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org>
GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
+the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to
-the Free Software Foundation, 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
In order to value number memory, we assign value numbers to vuses.
This enables us to note that, for example, stores to the same
address of the same value from the same starting memory states are
- equivalent.
+ equivalent.
TODO:
1. We can iterate only the changing portions of the SCC's, but
hashval_t hashcode;
tree result;
} *vn_binary_op_t;
+typedef const struct vn_binary_op_s *const_vn_binary_op_t;
/* Unary operations in the hashtable consist of a single operand, an
opcode, and a type. Result is the value number of the operation,
hashval_t hashcode;
tree result;
} *vn_unary_op_t;
+typedef const struct vn_unary_op_s *const_vn_unary_op_t;
/* Phi nodes in the hashtable consist of their non-VN_TOP phi
arguments, and the basic block the phi is in. Result is the value
hashval_t hashcode;
tree result;
} *vn_phi_t;
+typedef const struct vn_phi_s *const_vn_phi_t;
/* Reference operands only exist in reference operations structures.
They consist of an opcode, type, and some number of operands. For
tree op2;
} vn_reference_op_s;
typedef vn_reference_op_s *vn_reference_op_t;
+typedef const vn_reference_op_s *const_vn_reference_op_t;
DEF_VEC_O(vn_reference_op_s);
DEF_VEC_ALLOC_O(vn_reference_op_s, heap);
hashval_t hashcode;
tree result;
} *vn_reference_t;
+typedef const struct vn_reference_s *const_vn_reference_t;
/* Valid hashtables storing information we have proven to be
correct. */
}
/* Get the value numbering info for a given SSA name, creating it if
- it does not exist. */
+ it does not exist. */
vn_ssa_aux_t
VN_INFO_GET (tree name)
static int
vn_reference_op_eq (const void *p1, const void *p2)
{
- const vn_reference_op_t vro1 = (vn_reference_op_t) p1;
- const vn_reference_op_t vro2 = (vn_reference_op_t) p2;
+ const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
+ const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
return vro1->opcode == vro2->opcode
&& vro1->type == vro2->type
&& expressions_equal_p (vro1->op0, vro2->op0)
static hashval_t
vn_reference_hash (const void *p1)
{
- const vn_reference_t vr1 = (vn_reference_t) p1;
+ const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
return vr1->hashcode;
}
int i;
vn_reference_op_t vro;
- const vn_reference_t vr1 = (vn_reference_t) p1;
- const vn_reference_t vr2 = (vn_reference_t) p2;
+ const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
+ const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
if (vr1->vuses == vr2->vuses
&& vr1->operands == vr2->operands)
if (VEC_index (tree, vr2->vuses, i) != v)
return false;
}
-
+
for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
{
if (!vn_reference_op_eq (VEC_index (vn_reference_op_s, vr2->operands, i),
break;
default:
gcc_unreachable ();
-
+
}
VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
static hashval_t
vn_unary_op_hash (const void *p1)
{
- const vn_unary_op_t vuo1 = (vn_unary_op_t) p1;
+ const_vn_unary_op_t const vuo1 = (const_vn_unary_op_t) p1;
return vuo1->hashcode;
}
static int
vn_unary_op_eq (const void *p1, const void *p2)
{
- const vn_unary_op_t vuo1 = (vn_unary_op_t) p1;
- const vn_unary_op_t vuo2 = (vn_unary_op_t) p2;
+ const_vn_unary_op_t const vuo1 = (const_vn_unary_op_t) p1;
+ const_vn_unary_op_t const vuo2 = (const_vn_unary_op_t) p2;
return vuo1->opcode == vuo2->opcode
&& vuo1->type == vuo2->type
&& expressions_equal_p (vuo1->op0, vuo2->op0);
static hashval_t
vn_binary_op_hash (const void *p1)
{
- const vn_binary_op_t vbo1 = (vn_binary_op_t) p1;
+ const_vn_binary_op_t const vbo1 = (const_vn_binary_op_t) p1;
return vbo1->hashcode;
}
static int
vn_binary_op_eq (const void *p1, const void *p2)
{
- const vn_binary_op_t vbo1 = (vn_binary_op_t) p1;
- const vn_binary_op_t vbo2 = (vn_binary_op_t) p2;
+ const_vn_binary_op_t const vbo1 = (const_vn_binary_op_t) p1;
+ const_vn_binary_op_t const vbo2 = (const_vn_binary_op_t) p2;
return vbo1->opcode == vbo2->opcode
&& vbo1->type == vbo2->type
&& expressions_equal_p (vbo1->op0, vbo2->op0)
static hashval_t
vn_phi_hash (const void *p1)
{
- const vn_phi_t vp1 = (vn_phi_t) p1;
+ const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
return vp1->hashcode;
}
static int
vn_phi_eq (const void *p1, const void *p2)
{
- const vn_phi_t vp1 = (vn_phi_t) p1;
- const vn_phi_t vp2 = (vn_phi_t) p2;
+ const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
+ const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
if (vp1->block == vp2->block)
{
{
tree currval;
+ if (from != to
+ && TREE_CODE (to) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (to))
+ to = from;
+
/* The only thing we allow as value numbers are VN_TOP, ssa_names
and invariants. So assert that here. */
gcc_assert (to != NULL_TREE
/* Follow chains of copies to their destination. */
while (SSA_VAL (rhs) != rhs && TREE_CODE (SSA_VAL (rhs)) == SSA_NAME)
rhs = SSA_VAL (rhs);
-
+
/* The copy may have a more interesting constant filled expression
(we don't, since we know our RHS is just an SSA name). */
VN_INFO (lhs)->has_constants = VN_INFO (rhs)->has_constants;
bool allsame = true;
int i;
+ /* TODO: We could check for this in init_sccvn, and replace this
+ with a gcc_assert. */
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
+ return set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
+
/* See if all non-TOP arguments have the same value. TOP is
equivalent to everything, so we can ignore it. */
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
VN_INFO (PHI_RESULT (phi))->has_constants = false;
VN_INFO (PHI_RESULT (phi))->expr = sameval;
}
-
+
if (TREE_CODE (sameval) == SSA_NAME)
return visit_copy (PHI_RESULT (phi), sameval);
-
+
return set_ssa_val_to (PHI_RESULT (phi), sameval);
}
simplified. */
static tree
-simplify_binary_expression (tree rhs)
+simplify_binary_expression (tree stmt, tree rhs)
{
tree result = NULL_TREE;
tree op0 = TREE_OPERAND (rhs, 0);
op1 = SSA_VAL (op1);
}
+ /* Avoid folding if nothing changed. */
+ if (op0 == TREE_OPERAND (rhs, 0)
+ && op1 == TREE_OPERAND (rhs, 1))
+ return NULL_TREE;
+
+ fold_defer_overflow_warnings ();
+
result = fold_binary (TREE_CODE (rhs), TREE_TYPE (rhs), op0, op1);
+ fold_undefer_overflow_warnings (result && valid_gimple_expression_p (result),
+ stmt, 0);
+
/* Make sure result is not a complex expression consisting
of operators of operators (IE (a + b) + (a + c))
Otherwise, we will end up with unbounded expressions if
return NULL_TREE;
}
+/* Simplify the unary expression RHS, and return the result if
+ simplified. */
+
+static tree
+simplify_unary_expression (tree rhs)
+{
+ tree result = NULL_TREE;
+ tree op0 = TREE_OPERAND (rhs, 0);
+
+ if (TREE_CODE (op0) != SSA_NAME)
+ return NULL_TREE;
+
+ if (VN_INFO (op0)->has_constants)
+ op0 = valueize_expr (VN_INFO (op0)->expr);
+ else if (TREE_CODE (rhs) == NOP_EXPR
+ || TREE_CODE (rhs) == CONVERT_EXPR
+ || TREE_CODE (rhs) == REALPART_EXPR
+ || TREE_CODE (rhs) == IMAGPART_EXPR)
+ {
+ /* We want to do tree-combining on conversion-like expressions.
+ Make sure we feed only SSA_NAMEs or constants to fold though. */
+ tree tem = valueize_expr (VN_INFO (op0)->expr);
+ if (UNARY_CLASS_P (tem)
+ || BINARY_CLASS_P (tem)
+ || TREE_CODE (tem) == SSA_NAME
+ || is_gimple_min_invariant (tem))
+ op0 = tem;
+ }
+
+ /* Avoid folding if nothing changed, but remember the expression. */
+ if (op0 == TREE_OPERAND (rhs, 0))
+ return rhs;
+
+ result = fold_unary (TREE_CODE (rhs), TREE_TYPE (rhs), op0);
+ if (result)
+ {
+ STRIP_USELESS_TYPE_CONVERSION (result);
+ if (valid_gimple_expression_p (result))
+ return result;
+ }
+
+ return rhs;
+}
+
/* Try to simplify RHS using equivalences and constant folding. */
static tree
if (result)
return result;
}
- break;
+ /* Fallthrough for some codes. */
+ if (!(TREE_CODE (rhs) == REALPART_EXPR
+ || TREE_CODE (rhs) == IMAGPART_EXPR))
+ break;
/* We could do a little more with unary ops, if they expand
into binary ops, but it's debatable whether it is worth it. */
case tcc_unary:
- {
- tree result = NULL_TREE;
- tree op0 = TREE_OPERAND (rhs, 0);
- if (TREE_CODE (op0) == SSA_NAME && VN_INFO (op0)->has_constants)
- op0 = VN_INFO (op0)->expr;
- else if (TREE_CODE (op0) == SSA_NAME && SSA_VAL (op0) != op0)
- op0 = SSA_VAL (op0);
- result = fold_unary (TREE_CODE (rhs), TREE_TYPE (rhs), op0);
- if (result)
- return result;
- }
+ return simplify_unary_expression (rhs);
break;
case tcc_comparison:
case tcc_binary:
- return simplify_binary_expression (rhs);
+ return simplify_binary_expression (stmt, rhs);
break;
default:
break;
have been value numbering optimistically, and
iterating. They may become non-constant in this case,
even if they were optimistically constant. */
-
+
VN_INFO (lhs)->has_constants = false;
VN_INFO (lhs)->expr = lhs;
}
if (VEC_length (tree, scc) == 1)
{
tree use = VEC_index (tree, scc, 0);
- if (!VN_INFO (use)->use_processed)
+ if (!VN_INFO (use)->use_processed)
visit_use (use);
}
else
SSA_NAME_VALUE (name) = NULL;
}
}
-
+
VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
VEC_free (tree, heap, sccstack);
free_vn_table (valid_info);