This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: SCC based value numbering
- From: "Daniel Berlin" <dberlin at dberlin dot org>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Cc: dnovillo at google dot com
- Date: Tue, 29 May 2007 13:20:40 -0400
- Subject: [PATCH]: SCC based value numbering
This patch adds a reusable SCC based value numbering pass that
computes value numbers for our expressions.
It does a significantly better job than FRE/PRE's existing value
numbering, and could easily be made to subsume DOM's (which involves
watching edge tests and propagating the result).
It detects a significantly increased number of loads as equivalent
(about 20% on most cases), besides being able to do a better job with
scalar operations, and being able to value number phi nodes.
It is also easier to extend to do the kinds of simplifications that
Richard Guenther and others have expressed an interest in.
The new VN will even notice when two stores are stores of the same
value, and value number the vdefs so that value numbered loads using
those will be considered equivalent.
It also allow us to shortcut most of FRE now that the value numbering
is done for us.
Note that the PRE portion of the diff change is in slight flux, as i
am testing two ways of working around a problem where we've outsmarted
PRE (This is a PRE bug, not a VN one :P).
I have only included it to show how the new VN is used, so it's not in
the changelog. For review purposes, feel free to review anything in
the diff after Makefile.in
Bootstrapped and regtested on i686-darwin
Okay for mainline?
--Dan
2007-05-29 Daniel Berlin <dberlin@dberlin.org>
* tree-ssa-sccvn.c: New file
* tree-ssa-sccvn.h: Ditto
* Makefile.in (tree-ssa-sccvn.o): New.
Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c (.../trunk) (revision 0)
+++ gcc/tree-ssa-sccvn.c (.../branches/gcc-pre-vn) (revision 125165)
@@ -0,0 +1,1996 @@
+/* SCC value numbering for trees
+ Copyright (C) 2006
+ Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dan@dberlin.org>
+
+This file is part of GCC.
+
+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)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+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. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "tree.h"
+#include "basic-block.h"
+#include "diagnostic.h"
+#include "tree-inline.h"
+#include "tree-flow.h"
+#include "tree-gimple.h"
+#include "tree-dump.h"
+#include "timevar.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"
+#include "bitmap.h"
+#include "langhooks.h"
+#include "cfgloop.h"
+#include "tree-ssa-sccvn.h"
+
+/* This algorithm is based on the SCC algorithm presented by Keith
+ Cooper and L. Taylor Simpson in "SCC-Based Value numbering". In
+ straight line code, it is equivalent to a regular hash based value
+ numbering that is performed in reverse postorder.
+
+ For code with cycles, there are two alternatives, both of which
+ require keeping the hashtables separate from the actual list of
+ value numbers for SSA names.
+
+ 1. Iterate value numbering in an RPO walk of the blocks, removing
+ all the entries from the hashtable after each iteration (but
+ keeping the SSA name->value number mapping between iterations).
+ Iterate until it does not change.
+
+ 2. Perform value numbering as part of an SCC walk on the SSA graph,
+ iterating only the cycles in the SSA graph until they do not change
+ (using a separate, optimistic hashtable for value numbering the SCC
+ operands).
+
+ The second is not just faster in practice (because most SSA graph
+ cycles do not involve all the variables in the graph), it also has
+ some nice properties.
+
+ One of these nice properties is that when we pop an SCC off the
+ stack, we are guaranteed to have processed all the operands coming from
+ *outside of that SCC*, so we do not need to do anything special to
+ ensure they have value numbers.
+
+ Another nice property is that the SCC walk is done as part of a DFS
+ of the SSA graph, which makes it easy to perform combining and
+ simplifying operations at the same time.
+
+ The code below is deliberately written in a way that makes it easy
+ to separate the SCC walk from the other work it does.
+
+ In order to propagate constants through the code, we track which
+ expressions contain constants, and use those while folding. In
+ theory, we could also track expressions whose value numbers are
+ replaced, in case we end up folding based on expression
+ identities.
+
+ 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.
+ TODO:
+
+ 1. We can iterate only the changing portions of the SCC's, but
+ I have not seen an SCC big enough for this to be a win.
+ 2. If you differentiate between phi nodes for loops and phi nodes
+ for if-then-else, you can properly consider phi nodes in different
+ blocks for equivalence.
+ 3. We could value number vuses in more cases, particularly, whole
+ structure copies.
+*/
+
+/* The set of hashtables and alloc_pool's for their items. */
+
+typedef struct vn_tables_s
+{
+ htab_t unary;
+ htab_t binary;
+ htab_t phis;
+ htab_t references;
+ alloc_pool unary_op_pool;
+ alloc_pool binary_op_pool;
+ alloc_pool phis_pool;
+ alloc_pool references_pool;
+} *vn_tables_t;
+
+/* Binary operations in the hashtable consist of two operands, an
+ opcode, and a type. Result is the value number of the operation,
+ and hashcode is stored to avoid having to calculate it
+ repeatedly. */
+
+typedef struct vn_binary_op_s
+{
+ enum tree_code opcode;
+ tree type;
+ tree op0;
+ tree op1;
+ hashval_t hashcode;
+ tree result;
+} *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,
+ and hashcode is stored to avoid having to calculate it repeatedly. */
+
+typedef struct vn_unary_op_s
+{
+ enum tree_code opcode;
+ tree type;
+ tree op0;
+ hashval_t hashcode;
+ tree result;
+} *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
+ number of the operation, and hashcode is stored to avoid having to
+ calculate it repeatedly. Phi nodes not in the same block are never
+ considered equivalent. */
+
+typedef struct vn_phi_s
+{
+ VEC(tree, heap) *phiargs;
+ basic_block block;
+ hashval_t hashcode;
+ tree result;
+} *vn_phi_t;
+
+/* Reference operands only exist in reference operations structures.
+ They consist of an opcode, type, and some number of operands. For
+ a given opcode, some, all, or none of the operands may be used.
+ The operands are there to store the information that makes up the
+ portion of the addressing calculation that opcode performs. */
+
+typedef struct vn_reference_op_struct
+{
+ enum tree_code opcode;
+ tree type;
+ tree op0;
+ tree op1;
+ tree op2;
+} vn_reference_op_s;
+typedef vn_reference_op_s *vn_reference_op_t;
+
+DEF_VEC_O(vn_reference_op_s);
+DEF_VEC_ALLOC_O(vn_reference_op_s, heap);
+
+/* A reference operation in the hashtable is representation as a
+ collection of vuses, representing the memory state at the time of
+ the operation, and a collection of operands that make up the
+ addressing calculation. If two vn_reference_t's have the same set
+ of operands, they access the same memory location. We also store
+ the resulting value number, and the hashcode. The vuses are
+ always stored in order sorted by ssa name version. */
+
+typedef struct vn_reference_s
+{
+ VEC(tree, heap) *vuses;
+ VEC(vn_reference_op_s, heap) *operands;
+ hashval_t hashcode;
+ tree result;
+} *vn_reference_t;
+
+/* Valid hashtables storing information we have proven to be
+ correct. */
+
+static vn_tables_t valid_info;
+
+/* Optimistic hashtables storing information we are making assumptions
+ during iterations. */
+
+static vn_tables_t optimistic_info;
+
+/* Pointer to the set of hashtables that is currently being used.
+ Should always point to either the optimistic_info, or the
+ valid_info. */
+
+static vn_tables_t current_info;
+
+
+/* Reverse post order index for each basic block. */
+
+static int *rpo_numbers;
+
+#define SSA_VAL(x) (VN_INFO ((x))->valnum)
+
+/* This represents the top of the VN lattice, which is the universal
+ value. */
+
+tree VN_TOP;
+
+/* Next DFS number and the stack for strongly connected component
+ detection. */
+
+static unsigned int next_dfs_num;
+static VEC (tree, heap) *sccstack;
+
+DEF_VEC_P(vn_ssa_aux_t);
+DEF_VEC_ALLOC_P(vn_ssa_aux_t, heap);
+
+/* Table of vn_ssa_aux_t's, one per ssa_name. */
+
+static VEC (vn_ssa_aux_t, heap) *vn_ssa_aux_table;
+
+/* Return the value numbering information for a given SSA name. */
+
+vn_ssa_aux_t
+VN_INFO (tree name)
+{
+ return VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
+ SSA_NAME_VERSION (name));
+}
+
+/* Set the value numbering info for a given SSA name to a given
+ value. */
+
+static inline void
+VN_INFO_SET (tree name, vn_ssa_aux_t value)
+{
+ VEC_replace (vn_ssa_aux_t, vn_ssa_aux_table,
+ SSA_NAME_VERSION (name), value);
+}
+
+/* Compare two reference operands P1 and P2 for equality. return true if
+ they are equal, and false otherwise. */
+
+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;
+ return vro1->opcode == vro2->opcode
+ && vro1->type == vro2->type
+ && expressions_equal_p (vro1->op0, vro2->op0)
+ && expressions_equal_p (vro1->op1, vro2->op1)
+ && expressions_equal_p (vro1->op2, vro2->op2);
+}
+
+/* Compute the hash for a reference operand VRO1 */
+
+static hashval_t
+vn_reference_op_compute_hash (const vn_reference_op_t vro1)
+{
+ return iterative_hash_expr (vro1->op0, vro1->opcode)
+ + iterative_hash_expr (vro1->op1, vro1->opcode)
+ + iterative_hash_expr (vro1->op2, vro1->opcode);
+}
+
+/* Return the hashcode for a given reference operation P1. */
+
+static hashval_t
+vn_reference_hash (const void *p1)
+{
+ const vn_reference_t vr1 = (vn_reference_t) p1;
+ return vr1->hashcode;
+}
+
+/* Compute a hash for the reference operation VR1 and return it. */
+
+static inline hashval_t
+vn_reference_compute_hash (const vn_reference_t vr1)
+{
+ hashval_t result = 0;
+ tree v;
+ int i;
+ vn_reference_op_t vro;
+
+ for (i = 0; VEC_iterate (tree, vr1->vuses, i, v); i++)
+ result += iterative_hash_expr (v, 0);
+ for (i = 0; VEC_iterate (vn_reference_op_s, vr1->operands, i, vro); i++)
+ result += vn_reference_op_compute_hash (vro);
+
+ return result;
+}
+
+/* Return true if reference operations P1 and P2 are equivalent. This
+ means they have the same set of operands and vuses. */
+
+static int
+vn_reference_eq (const void *p1, const void *p2)
+{
+ tree v;
+ 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;
+
+ if (vr1->vuses == vr2->vuses
+ && vr1->operands == vr2->operands)
+ return true;
+
+ /* Impossible for them to be equivalent if they have different
+ number of vuses. */
+ if (VEC_length (tree, vr1->vuses) != VEC_length (tree, vr2->vuses))
+ return false;
+
+ /* We require that address operands be canonicalized in a way that
+ two memory references will have the same operands if they are
+ equivalent. */
+ if (VEC_length (vn_reference_op_s, vr1->operands)
+ != VEC_length (vn_reference_op_s, vr2->operands))
+ return false;
+
+ /* The memory state is more often different than the address of the
+ store/load, so check it first. */
+ for (i = 0; VEC_iterate (tree, vr1->vuses, i, v); i++)
+ {
+ 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),
+ vro))
+ return false;
+ }
+ return true;
+}
+
+/* Place the vuses from STMT into *result */
+
+static inline void
+vuses_to_vec (tree stmt, VEC (tree, heap) **result)
+{
+ ssa_op_iter iter;
+ tree vuse;
+
+ if (!stmt)
+ return;
+
+ FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
+ VEC_safe_push (tree, heap, *result, vuse);
+
+ if (VEC_length (tree, *result) > 1)
+ sort_vuses_heap (*result);
+}
+
+
+/* Copy the VUSE names in STMT into a vector, and return
+ the vector. */
+
+static VEC (tree, heap) *
+copy_vuses_from_stmt (tree stmt)
+{
+ VEC (tree, heap) *vuses = NULL;
+
+ vuses_to_vec (stmt, &vuses);
+
+ return vuses;
+}
+
+/* Place the vdefs from STMT into *result */
+
+static inline void
+vdefs_to_vec (tree stmt, VEC (tree, heap) **result)
+{
+ ssa_op_iter iter;
+ tree vdef;
+
+ if (!stmt)
+ return;
+
+ FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+ VEC_safe_push (tree, heap, *result, vdef);
+
+ if (VEC_length (tree, *result) > 1)
+ sort_vuses_heap (*result);
+}
+
+/* Copy the names of vdef results in STMT into a vector, and return
+ the vector. */
+
+static VEC (tree, heap) *
+copy_vdefs_from_stmt (tree stmt)
+{
+ VEC (tree, heap) *vdefs = NULL;
+
+ vdefs_to_vec (stmt, &vdefs);
+
+ return vdefs;
+}
+
+/* Place for shared_v{uses/defs}_from_stmt to shove vuses/vdefs. */
+static VEC (tree, heap) *shared_lookup_vops;
+
+/* Copy the virtual uses from STMT into SHARED_LOOKUP_VOPS.
+ This function will overwrite the current SHARED_LOOKUP_VOPS
+ variable. */
+
+static VEC (tree, heap) *
+shared_vuses_from_stmt (tree stmt)
+{
+ VEC_truncate (tree, shared_lookup_vops, 0);
+ vuses_to_vec (stmt, &shared_lookup_vops);
+
+ return shared_lookup_vops;
+}
+
+/* Copy the operations present in load/store/call REF into RESULT, a vector of
+ vn_reference_op_s's. */
+
+static void
+copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
+{
+ /* Calls are different from all other reference operations. */
+ if (TREE_CODE (ref) == CALL_EXPR)
+ {
+ vn_reference_op_s temp;
+ tree callfn;
+ call_expr_arg_iterator iter;
+ tree callarg;
+
+ /* Copy the call_expr opcode, type, function being called, and
+ arguments. */
+ memset(&temp, 0, sizeof (temp));
+ temp.type = TREE_TYPE (ref);
+ temp.opcode = CALL_EXPR;
+ VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
+
+ callfn = get_callee_fndecl (ref);
+ if (!callfn)
+ callfn = CALL_EXPR_FN (ref);
+ temp.type = TREE_TYPE (callfn);
+ temp.opcode = TREE_CODE (callfn);
+ temp.op0 = callfn;
+ VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
+
+ FOR_EACH_CALL_EXPR_ARG (callarg, iter, ref)
+ {
+ memset(&temp, 0, sizeof (temp));
+ temp.type = TREE_TYPE (callarg);
+ temp.opcode = TREE_CODE (callarg);
+ temp.op0 = callarg;
+ VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
+ }
+ return;
+ }
+
+ /* For non-calls, reference-opize the addressing info. */
+
+ while (ref)
+ {
+ vn_reference_op_s temp;
+ memset(&temp, 0, sizeof (temp));
+ temp.type = TREE_TYPE (ref);
+ temp.opcode = TREE_CODE (ref);
+
+ switch (temp.opcode)
+ {
+ case INDIRECT_REF:
+ /* The only operand is the address, which gets its own
+ vn_reference_op_s structure. */
+ break;
+ case BIT_FIELD_REF:
+ /* Record bits and position. */
+ temp.op0 = TREE_OPERAND (ref, 1);
+ temp.op1 = TREE_OPERAND (ref, 2);
+ break;
+ case COMPONENT_REF:
+ /* Record field as operand. */
+ temp.op0 = TREE_OPERAND (ref, 1);
+ break;
+ case ARRAY_REF:
+ /* Record index as operand. */
+ temp.op0 = TREE_OPERAND (ref, 1);
+ temp.op1 = TREE_OPERAND (ref, 3);
+ break;
+ case VAR_DECL:
+ case PARM_DECL:
+ case CONST_DECL:
+ case RESULT_DECL:
+ case SSA_NAME:
+ temp.op0 = ref;
+ break;
+ default:
+ break;
+ }
+ VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
+
+ if (REFERENCE_CLASS_P (ref))
+ ref = TREE_OPERAND (ref, 0);
+ else
+ ref = NULL_TREE;
+ }
+}
+
+/* Create a vector of vn_reference_op_s structures from REF, a
+ REFERENCE_CLASS_P tree. The vector is not shared. */
+
+static VEC(vn_reference_op_s, heap) *
+create_reference_ops_from_ref (tree ref)
+{
+ VEC (vn_reference_op_s, heap) *result = NULL;
+
+ copy_reference_ops_from_ref (ref, &result);
+ return result;
+}
+
+static VEC(vn_reference_op_s, heap) *shared_lookup_references;
+
+/* Create a vector of vn_reference_op_s structures from REF, a
+ REFERENCE_CLASS_P tree. The vector is shared among all callers of
+ this function. */
+
+static VEC(vn_reference_op_s, heap) *
+shared_reference_ops_from_ref (tree ref)
+{
+ if (!ref)
+ return NULL;
+ VEC_truncate (vn_reference_op_s, shared_lookup_references, 0);
+ copy_reference_ops_from_ref (ref, &shared_lookup_references);
+ return shared_lookup_references;
+}
+
+
+/* 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. */
+
+static VEC (vn_reference_op_s, heap) *
+valueize_refs (VEC (vn_reference_op_s, heap) *orig)
+{
+ vn_reference_op_t vro;
+ int i;
+
+ for (i = 0; VEC_iterate (vn_reference_op_s, orig, i, vro); i++)
+ {
+ if (vro->opcode == SSA_NAME
+ || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
+ vro->op0 = SSA_VAL (vro->op0);
+ }
+
+ return orig;
+}
+
+/* Transform any SSA_NAME's in ORIG, a vector of vuse trees, into
+ their value numbers. This is done in-place, and the vector passed
+ in is returned. */
+
+static VEC (tree, heap) *
+valueize_vuses (VEC (tree, heap) *orig)
+{
+ tree vuse;
+ int i;
+
+ for (i = 0; VEC_iterate (tree, orig, i, vuse); i++)
+ VEC_replace (tree, orig, i, SSA_VAL (vuse));
+
+
+ return orig;
+}
+
+/* Lookup OP in the current hash table, and return the resulting
+ value number if it exists in the hash table. Return NULL_TREE if
+ it does not exist in the hash table. */
+
+static tree
+vn_reference_lookup (tree op, VEC (tree, heap) *vuses)
+{
+ void **slot;
+ struct vn_reference_s vr1;
+
+ vr1.vuses = valueize_vuses (vuses);
+ vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
+ vr1.hashcode = vn_reference_compute_hash (&vr1);
+ slot = htab_find_slot_with_hash (current_info->references, &vr1, vr1.hashcode,
+ NO_INSERT);
+ if (!slot)
+ return NULL_TREE;
+
+ return ((vn_reference_t)*slot)->result;
+}
+
+/* Insert OP into the current hash table with a value number of
+ RESULT. */
+
+static void
+vn_reference_insert (tree op, tree result, VEC(tree, heap) *vuses)
+{
+ void **slot;
+ vn_reference_t vr1;
+
+ vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
+
+ vr1->vuses = valueize_vuses (vuses);
+ vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
+ vr1->hashcode = vn_reference_compute_hash (vr1);
+ vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result;
+
+ slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
+ INSERT);
+
+ /* Because we lookup stores using vuses, and value number failures
+ using the vdefs (see visit_reference_op_store for how and why),
+ it's possible that on failure we may try to insert an already
+ inserted store. This is not wrong, there is no ssa name for a
+ store that we could use as a differentiator anyway. Thus, unlike
+ the other lookup functions, you cannot gcc_assert (!*slot)
+ here. */
+
+
+ *slot = vr1;
+}
+
+
+/* Return the stored hashcode for a unary operation. */
+
+static hashval_t
+vn_unary_op_hash (const void *p1)
+{
+ const vn_unary_op_t vuo1 = (vn_unary_op_t) p1;
+ return vuo1->hashcode;
+}
+
+/* Hash a unary operation P1 and return the result. */
+
+static inline hashval_t
+vn_unary_op_compute_hash (const vn_unary_op_t vuo1)
+{
+ return iterative_hash_expr (vuo1->op0, vuo1->opcode);
+}
+
+/* Return true if P1 and P2, two unary operations, are equivalent. */
+
+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;
+ return vuo1->opcode == vuo2->opcode
+ && vuo1->type == vuo2->type
+ && expressions_equal_p (vuo1->op0, vuo2->op0);
+}
+
+/* Lookup OP in the current hash table, and return the resulting
+ value number if it exists in the hash table. Return NULL_TREE if
+ it does not exist in the hash table. */
+
+static tree
+vn_unary_op_lookup (tree op)
+{
+ void **slot;
+ struct vn_unary_op_s vuo1;
+
+ vuo1.opcode = TREE_CODE (op);
+ vuo1.type = TREE_TYPE (op);
+ vuo1.op0 = TREE_OPERAND (op, 0);
+
+ if (TREE_CODE (vuo1.op0) == SSA_NAME)
+ vuo1.op0 = SSA_VAL (vuo1.op0);
+
+ vuo1.hashcode = vn_unary_op_compute_hash (&vuo1);
+ slot = htab_find_slot_with_hash (current_info->unary, &vuo1, vuo1.hashcode,
+ NO_INSERT);
+ if (!slot)
+ return NULL_TREE;
+ return ((vn_unary_op_t)*slot)->result;
+}
+
+/* Insert OP into the current hash table with a value number of
+ RESULT. */
+
+static void
+vn_unary_op_insert (tree op, tree result)
+{
+ void **slot;
+ vn_unary_op_t vuo1 = (vn_unary_op_t) pool_alloc (current_info->unary_op_pool);
+
+ vuo1->opcode = TREE_CODE (op);
+ vuo1->type = TREE_TYPE (op);
+ vuo1->op0 = TREE_OPERAND (op, 0);
+ vuo1->result = result;
+
+ if (TREE_CODE (vuo1->op0) == SSA_NAME)
+ vuo1->op0 = SSA_VAL (vuo1->op0);
+
+ vuo1->hashcode = vn_unary_op_compute_hash (vuo1);
+ slot = htab_find_slot_with_hash (current_info->unary, vuo1, vuo1->hashcode,
+ INSERT);
+ gcc_assert (!*slot);
+ *slot = vuo1;
+}
+
+/* Compute and return the hash value for binary operation VBO1. */
+
+static inline hashval_t
+vn_binary_op_compute_hash (const vn_binary_op_t vbo1)
+{
+ return iterative_hash_expr (vbo1->op0, vbo1->opcode)
+ + iterative_hash_expr (vbo1->op1, vbo1->opcode);
+}
+
+/* Return the computed hashcode for binary operation P1. */
+
+static hashval_t
+vn_binary_op_hash (const void *p1)
+{
+ const vn_binary_op_t vbo1 = (vn_binary_op_t) p1;
+ return vbo1->hashcode;
+}
+
+/* Compare binary operations P1 and P2 and return true if they are
+ equivalent. */
+
+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;
+ return vbo1->opcode == vbo2->opcode
+ && vbo1->type == vbo2->type
+ && expressions_equal_p (vbo1->op0, vbo2->op0)
+ && expressions_equal_p (vbo1->op1, vbo2->op1);
+}
+
+/* Lookup OP in the current hash table, and return the resulting
+ value number if it exists in the hash table. Return NULL_TREE if
+ it does not exist in the hash table. */
+
+static tree
+vn_binary_op_lookup (tree op)
+{
+ void **slot;
+ struct vn_binary_op_s vbo1;
+
+ vbo1.opcode = TREE_CODE (op);
+ vbo1.type = TREE_TYPE (op);
+ vbo1.op0 = TREE_OPERAND (op, 0);
+ vbo1.op1 = TREE_OPERAND (op, 1);
+
+ if (TREE_CODE (vbo1.op0) == SSA_NAME)
+ vbo1.op0 = SSA_VAL (vbo1.op0);
+ if (TREE_CODE (vbo1.op1) == SSA_NAME)
+ vbo1.op1 = SSA_VAL (vbo1.op1);
+
+ if (tree_swap_operands_p (vbo1.op0, vbo1.op1, false)
+ && commutative_tree_code (vbo1.opcode))
+ {
+ tree temp = vbo1.op0;
+ vbo1.op0 = vbo1.op1;
+ vbo1.op1 = temp;
+ }
+
+ vbo1.hashcode = vn_binary_op_compute_hash (&vbo1);
+ slot = htab_find_slot_with_hash (current_info->binary, &vbo1, vbo1.hashcode,
+ NO_INSERT);
+ if (!slot)
+ return NULL_TREE;
+ return ((vn_binary_op_t)*slot)->result;
+}
+
+/* Insert OP into the current hash table with a value number of
+ RESULT. */
+
+static void
+vn_binary_op_insert (tree op, tree result)
+{
+ void **slot;
+ vn_binary_op_t vbo1;
+ vbo1 = (vn_binary_op_t) pool_alloc (current_info->binary_op_pool);
+
+ vbo1->opcode = TREE_CODE (op);
+ vbo1->type = TREE_TYPE (op);
+ vbo1->op0 = TREE_OPERAND (op, 0);
+ vbo1->op1 = TREE_OPERAND (op, 1);
+ vbo1->result = result;
+
+ if (TREE_CODE (vbo1->op0) == SSA_NAME)
+ vbo1->op0 = SSA_VAL (vbo1->op0);
+ if (TREE_CODE (vbo1->op1) == SSA_NAME)
+ vbo1->op1 = SSA_VAL (vbo1->op1);
+
+ if (tree_swap_operands_p (vbo1->op0, vbo1->op1, false)
+ && commutative_tree_code (vbo1->opcode))
+ {
+ tree temp = vbo1->op0;
+ vbo1->op0 = vbo1->op1;
+ vbo1->op1 = temp;
+ }
+ vbo1->hashcode = vn_binary_op_compute_hash (vbo1);
+ slot = htab_find_slot_with_hash (current_info->binary, vbo1, vbo1->hashcode,
+ INSERT);
+ gcc_assert (!*slot);
+
+ *slot = vbo1;
+}
+
+/* Compute a hashcode for PHI operation VP1 and return it. */
+
+static inline hashval_t
+vn_phi_compute_hash (vn_phi_t vp1)
+{
+ hashval_t result = 0;
+ int i;
+ tree phi1op;
+
+ result = vp1->block->index;
+
+ for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
+ {
+ if (phi1op == VN_TOP)
+ continue;
+ result += iterative_hash_expr (phi1op, result);
+ }
+
+ return result;
+}
+
+/* Return the computed hashcode for phi operation P1. */
+
+static hashval_t
+vn_phi_hash (const void *p1)
+{
+ const vn_phi_t vp1 = (vn_phi_t) p1;
+ return vp1->hashcode;
+}
+
+/* Compare two phi entries for equality, ignoring VN_TOP arguments. */
+
+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;
+
+ if (vp1->block == vp2->block)
+ {
+ int i;
+ tree phi1op;
+
+ /* Any phi in the same block will have it's arguments in the
+ same edge order, because of how we store phi nodes. */
+ for (i = 0; VEC_iterate (tree, vp1->phiargs, i, phi1op); i++)
+ {
+ tree phi2op = VEC_index (tree, vp2->phiargs, i);
+ if (phi1op == VN_TOP || phi2op == VN_TOP)
+ continue;
+ if (!expressions_equal_p (phi1op, phi2op))
+ return false;
+ }
+ return true;
+ }
+ return false;
+}
+
+static VEC(tree, heap) *shared_lookup_phiargs;
+
+/* Lookup PHI in the current hash table, and return the resulting
+ value number if it exists in the hash table. Return NULL_TREE if
+ it does not exist in the hash table. */
+
+static tree
+vn_phi_lookup (tree phi)
+{
+ void **slot;
+ struct vn_phi_s vp1;
+ int i;
+
+ VEC_truncate (tree, shared_lookup_phiargs, 0);
+
+ /* Canonicalize the SSA_NAME's to their value number. */
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ tree def = PHI_ARG_DEF (phi, i);
+ def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
+ VEC_safe_push (tree, heap, shared_lookup_phiargs, def);
+ }
+ vp1.phiargs = shared_lookup_phiargs;
+ vp1.block = bb_for_stmt (phi);
+ vp1.hashcode = vn_phi_compute_hash (&vp1);
+ slot = htab_find_slot_with_hash (current_info->phis, &vp1, vp1.hashcode,
+ NO_INSERT);
+ if (!slot)
+ return NULL_TREE;
+ return ((vn_phi_t)*slot)->result;
+}
+
+/* Insert PHI into the current hash table with a value number of
+ RESULT. */
+
+static void
+vn_phi_insert (tree phi, tree result)
+{
+ void **slot;
+ vn_phi_t vp1 = (vn_phi_t) pool_alloc (current_info->phis_pool);
+ int i;
+ VEC (tree, heap) *args = NULL;
+
+ /* Canonicalize the SSA_NAME's to their value number. */
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ tree def = PHI_ARG_DEF (phi, i);
+ def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
+ VEC_safe_push (tree, heap, args, def);
+ }
+ vp1->phiargs = args;
+ vp1->block = bb_for_stmt (phi);
+ vp1->result = result;
+ vp1->hashcode = vn_phi_compute_hash (vp1);
+
+ slot = htab_find_slot_with_hash (current_info->phis, vp1, vp1->hashcode,
+ INSERT);
+
+ /* Because we iterate over phi operations more than once, it's
+ possible the slot might already exist here, hence no assert.*/
+ *slot = vp1;
+}
+
+
+/* Print set of components in strongly connected component SCC to OUT. */
+
+static void
+print_scc (FILE *out, VEC (tree, heap) *scc)
+{
+ tree var;
+ unsigned int i;
+
+ fprintf (out, "SCC consists of: ");
+ for (i = 0; VEC_iterate (tree, scc, i, var); i++)
+ {
+ print_generic_expr (out, var, 0);
+ fprintf (out, " ");
+ }
+ fprintf (out, "\n");
+}
+
+/* Set the value number of FROM to TO, return true if it has changed
+ as a result. */
+
+static inline bool
+set_ssa_val_to (tree from, tree to)
+{
+ gcc_assert (to != NULL);
+
+ /* Make sure we don't create chains of copies, so that we get the
+ best value numbering. visit_copy has code to make sure this doesn't
+ happen, we are doing this here to assert that nothing else breaks
+ this. */
+ gcc_assert (TREE_CODE (to) != SSA_NAME
+ || TREE_CODE (SSA_VAL (to)) != SSA_NAME
+ || SSA_VAL (to) == to
+ || to == from);
+ /* The only thing we allow as value numbers are ssa_names and
+ invariants. So assert that here. */
+ gcc_assert (TREE_CODE (to) == SSA_NAME || is_gimple_min_invariant (to));
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Setting value number of ");
+ print_generic_expr (dump_file, from, 0);
+ fprintf (dump_file, " to ");
+ print_generic_expr (dump_file, to, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ if (SSA_VAL (from) != to)
+ {
+ SSA_VAL (from) = to;
+ return true;
+ }
+ return false;
+}
+
+/* Set all definitions in STMT to value number to themselves.
+ Return true if a value number changed. */
+
+static bool
+defs_to_varying (tree stmt)
+{
+ bool changed = false;
+ ssa_op_iter iter;
+ def_operand_p defp;
+
+ FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_ALL_DEFS)
+ {
+ tree def = DEF_FROM_PTR (defp);
+
+ VN_INFO (def)->use_processed = true;
+ changed |= set_ssa_val_to (def, def);
+ }
+ return changed;
+}
+
+/* Visit a copy between LHS and RHS, return true if the value number
+ changed. */
+
+static bool
+visit_copy (tree lhs, tree rhs)
+{
+
+ /* 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;
+ VN_INFO (lhs)->expr = VN_INFO (rhs)->expr;
+
+ return set_ssa_val_to (lhs, rhs);
+}
+
+/* Visit a unary operator RHS, value number it, and return true if the
+ value number of LHS has changed as a result. */
+
+static bool
+visit_unary_op (tree lhs, tree op)
+{
+ bool changed = false;
+ tree result = vn_unary_op_lookup (op);
+
+ if (result)
+ {
+ changed = set_ssa_val_to (lhs, result);
+ }
+ else
+ {
+ changed = set_ssa_val_to (lhs, lhs);
+ vn_unary_op_insert (op, lhs);
+ }
+
+ return changed;
+}
+
+/* Visit a binary operator RHS, value number it, and return true if the
+ value number of LHS has changed as a result. */
+
+static bool
+visit_binary_op (tree lhs, tree op)
+{
+ bool changed = false;
+ tree result = vn_binary_op_lookup (op);
+
+ if (result)
+ {
+ changed = set_ssa_val_to (lhs, result);
+ }
+ else
+ {
+ changed = set_ssa_val_to (lhs, lhs);
+ vn_binary_op_insert (op, lhs);
+ }
+
+ return changed;
+}
+
+/* Visit a load from a reference operator RHS, part of STMT, value number it,
+ and return true if the value number of the LHS has changed as a result. */
+
+static bool
+visit_reference_op_load (tree lhs, tree op, tree stmt)
+{
+ bool changed = false;
+ tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt));
+
+ if (result)
+ {
+ changed = set_ssa_val_to (lhs, result);
+ }
+ else
+ {
+ changed = set_ssa_val_to (lhs, lhs);
+ vn_reference_insert (op, lhs, copy_vuses_from_stmt (stmt));
+ }
+
+ return changed;
+}
+
+
+/* Visit a store to a reference operator LHS, part of STMT, value number it,
+ and return true if the value number of the LHS has changed as a result. */
+
+static bool
+visit_reference_op_store (tree lhs, tree op, tree stmt)
+{
+ bool changed = false;
+ tree result;
+ bool resultsame = false;
+
+ /* First we want to lookup using the *vuses* from the store and see
+ if there the last store to this location with the same address
+ had the same value.
+
+ The vuses represent the memory state before the store. If the
+ memory state, address, and value of the store is the same as the
+ last store to this location, then this store will produce the
+ same memory state as that store.
+
+ In this case the vdef versions for this store are value numbered to those
+ vuse versions, since they represent the same memory state after
+ this store.
+
+ Otherwise, the vdefs for the store are used when inserting into
+ the table, since the store generates a new memory state. */
+
+ result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt));
+
+ if (result)
+ {
+ if (TREE_CODE (result) == SSA_NAME)
+ result = SSA_VAL (result);
+ resultsame = expressions_equal_p (result, op);
+ }
+
+ if (!result || !resultsame)
+ {
+ VEC(tree, heap) *vdefs = copy_vdefs_from_stmt (stmt);
+ int i;
+ tree vdef;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "No store match\n");
+ fprintf (dump_file, "Value numbering store ");
+ print_generic_expr (dump_file, lhs, 0);
+ fprintf (dump_file, " to ");
+ print_generic_expr (dump_file, op, 0);
+ fprintf (dump_file, "\n");
+ }
+ /* Have to set value numbers before insert, since insert is
+ going to valueize the references in-place. */
+ for (i = 0; VEC_iterate (tree, vdefs, i, vdef); i++)
+ {
+ VN_INFO (vdef)->use_processed = true;
+ changed |= set_ssa_val_to (vdef, vdef);
+ }
+
+ vn_reference_insert (lhs, op, vdefs);
+ }
+ else
+ {
+ /* We had a match, so value number the vdefs to have the value
+ number of the vuses they came from. */
+ ssa_op_iter op_iter;
+ def_operand_p var;
+ vuse_vec_p vv;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Store matched earlier value,"
+ "value numbering store vdefs to matching vuses.\n");
+
+ FOR_EACH_SSA_VDEF_OPERAND (var, vv, stmt, op_iter)
+ {
+ tree def = DEF_FROM_PTR (var);
+ tree use;
+
+ /* Uh, if the vuse is a multiuse, we can't really do much
+ here, sadly, since we don't know which value number of
+ which vuse to use. */
+ if (VUSE_VECT_NUM_ELEM (*vv) != 1)
+ use = def;
+ else
+ use = VUSE_ELEMENT_VAR (*vv, 0);
+
+ VN_INFO (def)->use_processed = true;
+ changed |= set_ssa_val_to (def, SSA_VAL (use));
+ }
+ }
+
+ return changed;
+}
+
+/* Visit and value number PHI, return true if the value number
+ changed. */
+
+static bool
+visit_phi (tree phi)
+{
+ bool changed = false;
+ tree result;
+ tree sameval = VN_TOP;
+ bool allsame = true;
+ int i;
+
+ /* 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++)
+ {
+ tree def = PHI_ARG_DEF (phi, i);
+
+ if (TREE_CODE (def) == SSA_NAME)
+ def = SSA_VAL (def);
+ if (def == VN_TOP)
+ continue;
+ if (sameval == VN_TOP)
+ {
+ sameval = def;
+ }
+ else
+ {
+ if (!expressions_equal_p (def, sameval))
+ {
+ allsame = false;
+ break;
+ }
+ }
+ }
+
+ /* If all value numbered to the same value, the phi node has that
+ value. */
+ if (allsame)
+ {
+ if (is_gimple_min_invariant (sameval))
+ {
+ VN_INFO (PHI_RESULT (phi))->has_constants = true;
+ 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);
+ }
+
+ /* Otherwise, see if it is equivalent to a phi node in this block. */
+ result = vn_phi_lookup (phi);
+ if (result)
+ changed = set_ssa_val_to (PHI_RESULT (phi), result);
+ else
+ {
+ vn_phi_insert (phi, PHI_RESULT (phi));
+ VN_INFO (PHI_RESULT (phi))->has_constants = false;
+ VN_INFO (PHI_RESULT (phi))->expr = PHI_RESULT (phi);
+ changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));
+ }
+
+ return changed;
+}
+
+/* Return true if EXPR contains constants. */
+
+static bool
+expr_has_constants (tree expr)
+{
+ switch (TREE_CODE_CLASS (TREE_CODE (expr)))
+ {
+ case tcc_unary:
+ return is_gimple_min_invariant (TREE_OPERAND (expr, 0));
+
+ case tcc_binary:
+ return is_gimple_min_invariant (TREE_OPERAND (expr, 0))
+ || is_gimple_min_invariant (TREE_OPERAND (expr, 1));
+ /* Constants inside reference ops are rarely interesting, but
+ it can take a lot of looking to find them. */
+ case tcc_reference:
+ return false;
+ default:
+ return is_gimple_min_invariant (expr);
+ }
+ return false;
+}
+
+/* Replace SSA_NAMES in expr with their value numbers, and return the
+ result.
+ This is performed in place. */
+
+static tree
+valueize_expr (tree expr)
+{
+ switch (TREE_CODE_CLASS (TREE_CODE (expr)))
+ {
+ case tcc_unary:
+ if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
+ && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
+ TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
+ break;
+ case tcc_binary:
+ if (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
+ && SSA_VAL (TREE_OPERAND (expr, 0)) != VN_TOP)
+ TREE_OPERAND (expr, 0) = SSA_VAL (TREE_OPERAND (expr, 0));
+ if (TREE_CODE (TREE_OPERAND (expr, 1)) == SSA_NAME
+ && SSA_VAL (TREE_OPERAND (expr, 1)) != VN_TOP)
+ TREE_OPERAND (expr, 1) = SSA_VAL (TREE_OPERAND (expr, 1));
+ break;
+ default:
+ break;
+ }
+ return expr;
+}
+
+/* Simplify the binary expression RHS, and return the result if
+ simplified. */
+
+static tree
+simplify_binary_expression (tree rhs)
+{
+ tree result = NULL_TREE;
+ tree op0 = TREE_OPERAND (rhs, 0);
+ tree op1 = TREE_OPERAND (rhs, 1);
+
+ /* This will not catch every single case we could combine, but will
+ catch those with constants. The goal here is to simultaneously
+ combine constants between expressions, but avoid infinite
+ expansion of expressions during simplification. */
+ if (TREE_CODE (op0) == SSA_NAME)
+ {
+ if (VN_INFO (op0)->has_constants)
+ op0 = valueize_expr (VN_INFO (op0)->expr);
+ else if (SSA_VAL (op0) != VN_TOP && SSA_VAL (op0) != op0)
+ op0 = VN_INFO (op0)->valnum;
+ }
+
+ if (TREE_CODE (op1) == SSA_NAME)
+ {
+ if (VN_INFO (op1)->has_constants)
+ op1 = valueize_expr (VN_INFO (op1)->expr);
+ else if (SSA_VAL (op1) != VN_TOP && SSA_VAL (op1) != op1)
+ op1 = VN_INFO (op1)->valnum;
+ }
+ result = fold_binary (TREE_CODE (rhs), TREE_TYPE (rhs), op0, op1);
+
+ /* Make sure result is not a complex expression consiting
+ of operators of operators (IE (a + b) + (a + c))
+ Otherwise, we will end up with unbounded expressions if
+ fold does anything at all. */
+ if (result)
+ {
+ if (is_gimple_min_invariant (result))
+ return result;
+ else if (SSA_VAR_P (result))
+ return result;
+ else if (EXPR_P (result))
+ {
+ switch (TREE_CODE_CLASS (TREE_CODE (result)))
+ {
+ case tcc_unary:
+ {
+ tree op0 = TREE_OPERAND (result, 0);
+ if (!EXPR_P (op0))
+ return result;
+ }
+ break;
+ case tcc_binary:
+ {
+ tree op0 = TREE_OPERAND (result, 0);
+ tree op1 = TREE_OPERAND (result, 1);
+ if (!EXPR_P (op0) && !EXPR_P (op1))
+ return result;
+ }
+ break;
+ default:
+ break;
+ }
+ }
+ }
+ return NULL_TREE;
+}
+
+/* Try to simplify RHS using equivalences, constant folding, and black
+ magic. */
+
+static tree
+try_to_simplify (tree stmt, tree rhs)
+{
+ if (TREE_CODE (rhs) == SSA_NAME)
+ {
+ if (is_gimple_min_invariant (SSA_VAL (rhs)))
+ return SSA_VAL (rhs);
+ else if (VN_INFO (rhs)->has_constants)
+ return VN_INFO (rhs)->expr;
+ }
+ else
+ {
+ switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
+ {
+ /* For references, see if we find a result for the lookup,
+ and use it if we do. */
+
+ case tcc_reference:
+ {
+ tree result = vn_reference_lookup (rhs,
+ shared_vuses_from_stmt (stmt));
+ if (result)
+ return result;
+ }
+ 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;
+ }
+ break;
+ case tcc_binary:
+ {
+ return simplify_binary_expression (rhs);
+ }
+ break;
+ default:
+ break;
+ }
+ }
+ return rhs;
+}
+
+/* Visit and value number USE, return true if the value number
+ changed. */
+
+static bool
+visit_use (tree use)
+{
+ bool changed = false;
+ tree stmt = SSA_NAME_DEF_STMT (use);
+ stmt_ann_t ann;
+
+ VN_INFO (use)->use_processed = true;
+
+ gcc_assert (!SSA_NAME_IN_FREE_LIST (use));
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Value numbering ");
+ print_generic_expr (dump_file, use, 0);
+ fprintf (dump_file, " stmt = ");
+ print_generic_stmt (dump_file, stmt, 0);
+ }
+
+ /* RETURN_EXPR may have an embedded MODIFY_STMT. */
+ if (TREE_CODE (stmt) == RETURN_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
+ stmt = TREE_OPERAND (stmt, 0);
+
+ ann = stmt_ann (stmt);
+
+ /* Handle uninitialized uses. */
+ if (IS_EMPTY_STMT (stmt))
+ {
+ changed = set_ssa_val_to (use, use);
+ }
+ else
+ {
+ if (TREE_CODE (stmt) == PHI_NODE)
+ {
+ changed = visit_phi (stmt);
+ }
+ else if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
+ || (ann && ann->has_volatile_ops))
+ {
+ changed = defs_to_varying (stmt);
+ }
+ else
+ {
+ tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ tree simplified;
+
+ STRIP_USELESS_TYPE_CONVERSION (rhs);
+
+ simplified = try_to_simplify (stmt, rhs);
+ if (simplified && simplified != rhs)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "RHS ");
+ print_generic_expr (dump_file, rhs, 0);
+ fprintf (dump_file, " simplified to ");
+ print_generic_expr (dump_file, simplified, 0);
+ if (TREE_CODE (lhs) == SSA_NAME)
+ fprintf (dump_file, " has constants %d\n",
+ VN_INFO (lhs)->has_constants);
+ else
+ fprintf (dump_file, "\n");
+
+ }
+ }
+ /* Setting value numbers to constants will screw up phi
+ congruence because constants are not uniquely
+ associated with a single ssa name that can be looked up.
+ */
+ if (simplified && is_gimple_min_invariant (simplified)
+ && TREE_CODE (lhs) == SSA_NAME
+ && simplified != rhs)
+ {
+ VN_INFO (lhs)->expr = simplified;
+ VN_INFO (lhs)->has_constants = true;
+ changed = set_ssa_val_to (lhs, simplified);
+ goto done;
+ }
+ else if (simplified && TREE_CODE (simplified) == SSA_NAME
+ && TREE_CODE (lhs) == SSA_NAME)
+ {
+ changed = visit_copy (lhs, simplified);
+ goto done;
+ }
+ else if (simplified)
+ {
+ tree oldrhs = rhs;
+
+ if (TREE_CODE (lhs) == SSA_NAME)
+ {
+ VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
+ /* We have to unshare the expression or else
+ valuizing may change the IL stream. */
+ VN_INFO (lhs)->expr = unshare_expr (simplified);
+ }
+ rhs = simplified;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "RHS ");
+ print_generic_expr (dump_file, oldrhs, 0);
+ fprintf (dump_file, " simplified to ");
+ print_generic_expr (dump_file, simplified, 0);
+ if (TREE_CODE (lhs) == SSA_NAME)
+ fprintf (dump_file, " has constants %d\n",
+ VN_INFO (lhs)->has_constants);
+ else
+ fprintf (dump_file, "\n");
+
+ }
+ }
+ else if (expr_has_constants (rhs) && TREE_CODE (lhs) == SSA_NAME)
+ {
+ VN_INFO (lhs)->has_constants = true;
+ VN_INFO (lhs)->expr = unshare_expr (rhs);
+ }
+ else if (TREE_CODE (lhs) == SSA_NAME)
+ {
+ /* We reset expr and constantness here because we may
+ 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 (TREE_CODE (lhs) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+ changed = defs_to_varying (stmt);
+ else if (REFERENCE_CLASS_P (lhs))
+ {
+ changed = visit_reference_op_store (lhs, rhs, stmt);
+ }
+ else if (TREE_CODE (lhs) == SSA_NAME)
+ {
+ if (is_gimple_min_invariant (rhs))
+ {
+ VN_INFO (lhs)->has_constants = true;
+ VN_INFO (lhs)->expr = rhs;
+ changed = set_ssa_val_to (lhs, rhs);
+ }
+ else if (TREE_CODE (rhs) == SSA_NAME)
+ changed = visit_copy (lhs, rhs);
+ else
+ {
+ switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
+ {
+ case tcc_unary:
+ changed = visit_unary_op (lhs, rhs);
+ break;
+ case tcc_binary:
+ changed = visit_binary_op (lhs, rhs);
+ break;
+ /* If tcc_vl_expr ever encompasses more than
+ CALL_EXPR, this will need to be changed. */
+ case tcc_vl_exp:
+ if (call_expr_flags (rhs) & (ECF_PURE | ECF_CONST))
+ changed = visit_reference_op_load (lhs, rhs, stmt);
+ else
+ changed = defs_to_varying (stmt);
+ break;
+ case tcc_declaration:
+ case tcc_reference:
+ changed = visit_reference_op_load (lhs, rhs, stmt);
+ break;
+ case tcc_expression:
+ if (TREE_CODE (rhs) == ADDR_EXPR)
+ {
+ changed = visit_unary_op (lhs, rhs);
+ goto done;
+ }
+ /* Fallthrough. */
+ default:
+ changed = defs_to_varying (stmt);
+ break;
+ }
+ }
+ }
+ else
+ changed = defs_to_varying (stmt);
+ }
+ }
+ done:
+ return changed;
+}
+
+/* Compare two operands by reverse postorder index */
+
+static int
+compare_ops (const void *pa, const void *pb)
+{
+ const tree opa = *((const tree *)pa);
+ const tree opb = *((const tree *)pb);
+ tree opstmta = SSA_NAME_DEF_STMT (opa);
+ tree opstmtb = SSA_NAME_DEF_STMT (opb);
+ basic_block bba;
+ basic_block bbb;
+
+ if (IS_EMPTY_STMT (opstmta) && IS_EMPTY_STMT (opstmtb))
+ return 0;
+ else if (IS_EMPTY_STMT (opstmta))
+ return -1;
+ else if (IS_EMPTY_STMT (opstmtb))
+ return 1;
+
+ bba = bb_for_stmt (opstmta);
+ bbb = bb_for_stmt (opstmtb);
+
+ if (!bba && !bbb)
+ return 0;
+ else if (!bba)
+ return -1;
+ else if (!bbb)
+ return 1;
+
+ if (bba == bbb)
+ {
+ if (TREE_CODE (opstmta) == PHI_NODE && TREE_CODE (opstmtb) == PHI_NODE)
+ return 0;
+ else if (TREE_CODE (opstmta) == PHI_NODE)
+ return -1;
+ else if (TREE_CODE (opstmtb) == PHI_NODE)
+ return 1;
+ return stmt_ann (opstmta)->uid - stmt_ann (opstmtb)->uid;
+ }
+ return rpo_numbers[bba->index] - rpo_numbers[bbb->index];
+}
+
+/* Sort an array containing members of a strongly connected component
+ SCC so that the members are ordered by RPO number.
+ This means that when the sort is complete, iterating through the
+ array will give you the members in RPO order. */
+
+static void
+sort_scc (VEC (tree, heap) *scc)
+{
+ qsort (VEC_address (tree, scc),
+ VEC_length (tree, scc),
+ sizeof (tree),
+ compare_ops);
+}
+
+/* Process a strongly connected component in the SSA graph. */
+
+static void
+process_scc (VEC (tree, heap) *scc)
+{
+ /* If the SCC has a single member, just visit it. */
+
+ if (VEC_length (tree, scc) == 1)
+ {
+ tree use = VEC_index (tree, scc, 0);
+ // if (!VN_INFO (use)->use_processed)
+ visit_use (use);
+ }
+ else
+ {
+ tree var;
+ unsigned int i;
+ unsigned int iterations = 0;
+ bool changed = true;
+
+ /* Iterate over the SCC with the optimistic table until it stops
+ changing. */
+ current_info = optimistic_info;
+ while (changed)
+ {
+ changed = false;
+ iterations++;
+ for (i = 0; VEC_iterate (tree, scc, i, var); i++)
+ changed |= visit_use (var);
+ }
+
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, "Processing SCC required %d iterations\n",
+ iterations);
+
+ /* Finally, visit the SCC once using the valid table. */
+ current_info = valid_info;
+ for (i = 0; VEC_iterate (tree, scc, i, var); i++)
+ visit_use (var);
+ }
+}
+
+/* Depth first search on NAME to discover and process SCC's in the SSA
+ graph.
+ Execution of this algorithm relies on the fact that the SCC's are
+ popped off the stack in topological order. */
+
+static void
+DFS (tree name)
+{
+ ssa_op_iter iter;
+ use_operand_p usep;
+ tree defstmt;
+
+ /* SCC info */
+ VN_INFO (name)->dfsnum = next_dfs_num++;
+ VN_INFO (name)->visited = true;
+ VN_INFO (name)->low = VN_INFO (name)->dfsnum;
+
+ VEC_safe_push (tree, heap, sccstack, name);
+ VN_INFO (name)->on_sccstack = true;
+ defstmt = SSA_NAME_DEF_STMT (name);
+
+ /* Recursively DFS on our operands, looking for SCC's. */
+ if (!IS_EMPTY_STMT (defstmt))
+ {
+ FOR_EACH_PHI_OR_STMT_USE (usep, SSA_NAME_DEF_STMT (name), iter,
+ SSA_OP_ALL_USES)
+ {
+ tree use = USE_FROM_PTR (usep);
+
+ /* Since we handle phi nodes, we will sometimes get
+ invariants in the use expression. */
+ if (TREE_CODE (use) != SSA_NAME)
+ continue;
+
+ if (! (VN_INFO (use)->visited))
+ {
+ DFS (use);
+ VN_INFO (name)->low = MIN (VN_INFO (name)->low,
+ VN_INFO (use)->low);
+ }
+ if (VN_INFO (use)->dfsnum < VN_INFO (name)->dfsnum
+ && VN_INFO (use)->on_sccstack)
+ {
+ VN_INFO (name)->low = MIN (VN_INFO (use)->dfsnum,
+ VN_INFO (name)->low);
+ }
+ }
+ }
+
+ /* See if we found an SCC. */
+ if (VN_INFO (name)->low == VN_INFO (name)->dfsnum)
+ {
+ VEC (tree, heap) *scc = NULL;
+ tree x;
+
+ /* Found an SCC, pop the components off the SCC stack and
+ process them. */
+ do
+ {
+ x = VEC_pop (tree, sccstack);
+
+ VN_INFO (x)->on_sccstack = false;
+ VEC_safe_push (tree, heap, scc, x);
+ } while (x != name);
+
+ if (VEC_length (tree, scc) > 1)
+ sort_scc (scc);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ print_scc (dump_file, scc);
+
+ process_scc (scc);
+
+ VEC_free (tree, heap, scc);
+ }
+}
+
+static void
+free_phi (void *vp)
+{
+ vn_phi_t phi = vp;
+ VEC_free (tree, heap, phi->phiargs);
+}
+
+
+/* Free a reference operation structure VP. */
+
+static void
+free_reference (void *vp)
+{
+ vn_reference_t vr = vp;
+ VEC_free (tree, heap, vr->vuses);
+ VEC_free (vn_reference_op_s, heap, vr->operands);
+}
+
+/* Allocate a value number table. */
+
+static void
+allocate_vn_table (vn_tables_t table)
+{
+ table->phis = htab_create (23, vn_phi_hash, vn_phi_eq, free_phi);
+ table->unary = htab_create (23, vn_unary_op_hash, vn_unary_op_eq, NULL);
+ table->binary = htab_create (23, vn_binary_op_hash, vn_binary_op_eq, NULL);
+ table->references = htab_create (23, vn_reference_hash, vn_reference_eq,
+ free_reference);
+
+ table->unary_op_pool = create_alloc_pool ("VN unary operations",
+ sizeof (struct vn_unary_op_s),
+ 30);
+ table->binary_op_pool = create_alloc_pool ("VN binary operations",
+ sizeof (struct vn_binary_op_s),
+ 30);
+ table->phis_pool = create_alloc_pool ("VN phis",
+ sizeof (struct vn_phi_s),
+ 30);
+ table->references_pool = create_alloc_pool ("VN references",
+ sizeof (struct vn_reference_s),
+ 30);
+}
+
+/* Free a value number table. */
+
+static void
+free_vn_table (vn_tables_t table)
+{
+ htab_delete (table->phis);
+ htab_delete (table->unary);
+ htab_delete (table->binary);
+ htab_delete (table->references);
+ free_alloc_pool (table->unary_op_pool);
+ free_alloc_pool (table->binary_op_pool);
+ free_alloc_pool (table->phis_pool);
+ free_alloc_pool (table->references_pool);
+}
+
+static void
+init_scc_vn (void)
+{
+ size_t i;
+ int j;
+ int *rpo_numbers_temp;
+ basic_block bb;
+ size_t id = 0;
+
+ calculate_dominance_info (CDI_DOMINATORS);
+ sccstack = NULL;
+ next_dfs_num = 1;
+
+ vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
+ /* VEC_alloc doesn't actually grow it to the right size, it just
+ preallocates the space to do so. */
+ VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
+ shared_lookup_phiargs = NULL;
+ shared_lookup_vops = NULL;
+ shared_lookup_references = NULL;
+ rpo_numbers = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+ rpo_numbers_temp = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+ pre_and_rev_post_order_compute (NULL, rpo_numbers_temp, false);
+
+ /* RPO numbers is an array of rpo ordering, rpo[i] = bb means that
+ the i'th block in RPO order is bb. We want to map bb's to RPO
+ numbers, so we need to rearrange this array. */
+ for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
+ rpo_numbers[rpo_numbers_temp[j]] = j;
+
+ free (rpo_numbers_temp);
+
+ VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
+
+ /* Create the VN_INFO structures, and initialize value numbers to
+ TOP. */
+ for (i = 0; i < num_ssa_names; i++)
+ {
+ tree name = ssa_name (i);
+ if (name)
+ {
+ VN_INFO_SET (name, XCNEW (struct vn_ssa_aux));
+ VN_INFO (name)->valnum = VN_TOP;
+ VN_INFO (name)->expr = name;
+ }
+ }
+
+ FOR_ALL_BB (bb)
+ {
+ block_stmt_iterator bsi;
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ stmt_ann (stmt)->uid = id++;
+ }
+ }
+
+ /* Create the valid and optimistic value numbering tables. */
+ valid_info = XCNEW (struct vn_tables_s);
+ allocate_vn_table (valid_info);
+ optimistic_info = XCNEW (struct vn_tables_s);
+ allocate_vn_table (optimistic_info);
+}
+
+void
+free_scc_vn (void)
+{
+ size_t i;
+
+ VEC_free (tree, heap, shared_lookup_phiargs);
+ VEC_free (tree, heap, shared_lookup_vops);
+ VEC_free (vn_reference_op_s, heap, shared_lookup_references);
+ XDELETEVEC (rpo_numbers);
+ for (i = 0; i < num_ssa_names; i++)
+ {
+ tree name = ssa_name (i);
+ if (name)
+ XDELETE (VN_INFO (name));
+ }
+ VEC_free (vn_ssa_aux_t, heap, vn_ssa_aux_table);
+ VEC_free (tree, heap, sccstack);
+ free_vn_table (valid_info);
+ XDELETE (valid_info);
+ free_vn_table (optimistic_info);
+ XDELETE (optimistic_info);
+}
+
+void
+run_scc_vn (void)
+{
+ size_t i;
+ tree param;
+
+ init_scc_vn ();
+ current_info = valid_info;
+
+ for (param = DECL_ARGUMENTS (current_function_decl);
+ param;
+ param = TREE_CHAIN (param))
+ {
+ if (gimple_default_def (cfun, param) != NULL)
+ {
+ tree def = gimple_default_def (cfun, param);
+ SSA_VAL (def) = def;
+ }
+ }
+
+ for (i = num_ssa_names - 1; i > 0; i--)
+ {
+ tree name = ssa_name (i);
+ if (name
+ && VN_INFO (name)->visited == false
+ && !has_zero_uses (name))
+ DFS (name);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Value numbers:\n");
+ for (i = 0; i < num_ssa_names; i++)
+ {
+ tree name = ssa_name (i);
+ if (name && VN_INFO (name)->visited
+ && (SSA_VAL (name) != name
+ || is_gimple_min_invariant (VN_INFO (name)->expr)))
+ {
+ print_generic_expr (dump_file, name, 0);
+ fprintf (dump_file, " = ");
+ if (is_gimple_min_invariant (VN_INFO (name)->expr))
+ print_generic_expr (dump_file, VN_INFO (name)->expr, 0);
+ else
+ print_generic_expr (dump_file, SSA_VAL (name), 0);
+ fprintf (dump_file, "\n");
+ }
+ }
+ }
+}
Index: gcc/tree-ssa-sccvn.h
===================================================================
--- gcc/tree-ssa-sccvn.h (.../trunk) (revision 0)
+++ gcc/tree-ssa-sccvn.h (.../branches/gcc-pre-vn) (revision 125165)
@@ -0,0 +1,54 @@
+/* Tree SCC value numbering
+ Copyright (C) 2007 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dberlin@dberlin.org>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; if not, write to the Free Software
+Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+*/
+
+#ifndef TREE_SSA_SCCVN_H
+#define TREE_SSA_SCCVN_H
+
+/* TOP of the VN lattice. */
+extern tree VN_TOP;
+
+typedef struct vn_ssa_aux
+{
+ /* SCC information. */
+ unsigned int dfsnum;
+ bool visited;
+ unsigned int low;
+ bool on_sccstack;
+
+ /* Value number. This may be an SSA name or a constant. */
+ tree valnum;
+ /* Representative expression, if not a direct constant. */
+ tree expr;
+ /* Whether the representative expression contains constants. */
+ bool has_constants;
+ /* Whether the SSA_NAME has been value numbered already. This is
+ only saying whether visit_use has been called on it at least
+ once. It cannot be used to avoid visitation for SSA_NAME's
+ involved in non-singleton SCC's. */
+ bool use_processed;
+} *vn_ssa_aux_t;
+
+/* Return the value numbering info for an SSA_NAME. */
+extern vn_ssa_aux_t VN_INFO (tree);
+void run_scc_vn (void);
+void free_scc_vn (void);
+
+#endif /* TREE_SSA_SCCVN_H */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-1.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-1.c (.../branches/gcc-pre-vn) (revision 125165)
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre-stats" } */
+
+void vnum_test8(int *data)
+{
+ int i;
+ int stop = data[3];
+ int m = data[4];
+ int n = m;
+ for (i=0; i<stop; i++) {
+ int k = data[2];
+ data[k] = 2;
+ data[0] = m - n;
+ k = data[1];
+ m = m + k;
+ n = n + k;
+ }
+}
+/* We should eliminate m - n, and set n = n + k into n = m. */
+/* { dg-final { scan-tree-dump-times "Eliminated: 2" 1 "fre"} } */
+/* { dg-final { cleanup-tree-dump "fre" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c (.../branches/gcc-pre-vn) (revision 125165)
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre-stats" } */
+
+int vnum_test8(int *data)
+{
+ int i;
+ int stop = data[3];
+ int m = data[4];
+ int n = m;
+ int p;
+ for (i=0; i<stop; i++) {
+ int k = data[2];
+ data[k] = 2;
+ data[0] = m - n;
+ k = data[1];
+ m = m + k;
+ n = n + k;
+ p = data[0];
+ }
+ return p;
+}
+/* We should eliminate m - n, and set n = n + k into n = m, and
+ set p to 0 */
+/* { dg-final { scan-tree-dump-times "Eliminated: 3" 1 "fre"} } */
+/* { dg-final { cleanup-tree-dump "fre" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-3.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-3.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-3.c (.../branches/gcc-pre-vn) (revision 125165)
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre-stats" } */
+int main(int argc, char **argv)
+{
+ int *p;
+ int result;
+ *p = 2;
+ if (argc)
+ *p = 2;
+ result = *p;
+ return result;
+}
+/* We should eliminate result = *p by saying it has the value 2. */
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "fre"} } */
+/* { dg-final { cleanup-tree-dump "fre" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-4.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-4.c (.../trunk) (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-4.c (.../branches/gcc-pre-vn) (revision 125165)
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre-stats" } */
+
+int vnum_test8(int *data)
+{
+ int i;
+ int stop = data[3];
+ int m = data[4];
+ int n = m;
+ int p = 0;
+
+ for (i=0; i<stop; i++) {
+ int k = data[2];
+ data[5] = 0;
+ if (i < 30)
+ data[5] = m - n;
+ p = data[5];
+ k = data[1];
+ m = m + k;
+ n = n + k;
+ }
+ return p;
+}
+/* We should eliminate m - n, n + k, set data[5] = 0, eliminate the
+ address arithmetic for data[5], and set p = 0.
+/* { dg-final { scan-tree-dump-times "Eliminated: 5" 1 "fre"} } */
+/* { dg-final { cleanup-tree-dump "fre" } } */
Index: gcc/tree-vn.c
===================================================================
--- gcc/tree-vn.c (.../trunk) (revision 125031)
+++ gcc/tree-vn.c (.../branches/gcc-pre-vn) (revision 125165)
@@ -55,12 +55,9 @@ typedef struct val_expr_pair_d
hashval_t hashcode;
} *val_expr_pair_t;
-static void set_value_handle (tree e, tree v);
-
-
/* Create and return a new value handle node of type TYPE. */
-static tree
+tree
make_value_handle (tree type)
{
static unsigned int id = 0;
@@ -175,7 +172,7 @@ val_expr_pair_expr_eq (const void *p1, c
/* Set the value handle for expression E to value V. */
-static void
+void
set_value_handle (tree e, tree v)
{
if (TREE_CODE (e) == SSA_NAME)
@@ -394,6 +391,19 @@ sort_vuses (VEC (tree,gc) *vuses)
vuses_compare);
}
+/* Sort the VUSE array so that we can do equality comparisons
+ quicker on two vuse vecs. */
+
+void
+sort_vuses_heap (VEC (tree,heap) *vuses)
+{
+ if (VEC_length (tree, vuses) > 1)
+ qsort (VEC_address (tree, vuses),
+ VEC_length (tree, vuses),
+ sizeof (tree),
+ vuses_compare);
+}
+
/* Like vn_lookup, but creates a new value for expression EXPR, if
EXPR doesn't already have a value. Return the existing/created
value for EXPR. STMT represents the stmt associated with EXPR. It is used
Index: gcc/tree-flow.h
===================================================================
--- gcc/tree-flow.h (.../trunk) (revision 125031)
+++ gcc/tree-flow.h (.../branches/gcc-pre-vn) (revision 125165)
@@ -1082,10 +1082,13 @@ void print_value_expressions (FILE *, tr
/* In tree-vn.c */
+tree make_value_handle (tree);
+void set_value_handle (tree, tree);
bool expressions_equal_p (tree, tree);
static inline tree get_value_handle (tree);
hashval_t vn_compute (tree, hashval_t);
void sort_vuses (VEC (tree, gc) *);
+void sort_vuses_heap (VEC (tree, heap) *);
tree vn_lookup_or_add (tree, tree);
tree vn_lookup_or_add_with_vuses (tree, VEC (tree, gc) *);
void vn_add (tree, tree);
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in (.../trunk) (revision 125031)
+++ gcc/Makefile.in (.../branches/gcc-pre-vn) (revision 125165)
@@ -1132,6 +1132,7 @@ OBJS-common = \
tree-ssa-pre.o \
tree-ssa-propagate.o \
tree-ssa-reassoc.o \
+ tree-ssa-sccvn.o \
tree-ssa-sink.o \
tree-ssa-structalias.o \
tree-ssa-ter.o \
@@ -1992,7 +1993,12 @@ tree-ssa-pre.o : tree-ssa-pre.c $(TREE_F
$(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
$(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) $(CFGLOOP_H) \
alloc-pool.h $(BASIC_BLOCK_H) bitmap.h $(HASHTAB_H) $(TREE_GIMPLE_H) \
- $(TREE_INLINE_H) tree-iterator.h
+ $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h
+tree-ssa-sccvn.o : tree-ssa-sccvn.c $(TREE_FLOW_H) $(CONFIG_H) \
+ $(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
+ $(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) $(CFGLOOP_H) \
+ alloc-pool.h $(BASIC_BLOCK_H) bitmap.h $(HASHTAB_H) $(TREE_GIMPLE_H) \
+ $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h
tree-vn.o : tree-vn.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(GGC_H) \
$(TREE_H) $(TREE_FLOW_H) $(HASHTAB_H) langhooks.h tree-pass.h \
$(TREE_DUMP_H) $(DIAGNOSTIC_H)
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c (.../trunk) (revision 125031)
+++ gcc/tree-ssa-pre.c (.../branches/gcc-pre-vn) (revision 125165)
@@ -45,6 +45,7 @@ Boston, MA 02110-1301, USA. */
#include "bitmap.h"
#include "langhooks.h"
#include "cfgloop.h"
+#include "tree-ssa-sccvn.h"
/* TODO:
@@ -649,9 +650,8 @@ bitmap_set_and (bitmap_set_t dest, bitma
if (dest != orig)
{
bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
-
+
bitmap_and_into (dest->values, orig->values);
-
bitmap_copy (temp, dest->expressions);
EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
{
@@ -943,11 +943,15 @@ find_leader_in_sets (tree expr, bitmap_s
static tree
phi_translate (tree expr, bitmap_set_t set1, bitmap_set_t set2,
- basic_block pred, basic_block phiblock)
+ basic_block pred, basic_block phiblock, int depth)
{
tree phitrans = NULL;
tree oldexpr = expr;
+ depth++;
+
+ gcc_assert (depth < 50);
+
if (expr == NULL)
return NULL;
@@ -993,7 +997,7 @@ phi_translate (tree expr, bitmap_set_t s
VEC (tree, gc) *tvuses;
newfn = phi_translate (find_leader_in_sets (oldfn, set1, set2),
- set1, set2, pred, phiblock);
+ set1, set2, pred, phiblock, depth);
if (newfn == NULL)
return NULL;
if (newfn != oldfn)
@@ -1004,7 +1008,7 @@ phi_translate (tree expr, bitmap_set_t s
if (oldsc)
{
newsc = phi_translate (find_leader_in_sets (oldsc, set1, set2),
- set1, set2, pred, phiblock);
+ set1, set2, pred, phiblock, depth);
if (newsc == NULL)
return NULL;
if (newsc != oldsc)
@@ -1037,7 +1041,7 @@ phi_translate (tree expr, bitmap_set_t s
return NULL;
oldval = find_leader_in_sets (oldval, set1, set2);
newval = phi_translate (oldval, set1, set2, pred,
- phiblock);
+ phiblock, depth);
if (newval == NULL)
return NULL;
if (newval != oldval)
@@ -1068,9 +1072,9 @@ phi_translate (tree expr, bitmap_set_t s
tvuses = translate_vuses_through_block (vuses, phiblock, pred);
if (vuses != tvuses && ! newexpr)
- newexpr = temp_copy_call_expr (expr);
+ newexpr = temp_copy_call_expr (expr);
- if (newexpr)
+ if (newexpr)
{
newexpr->base.ann = NULL;
vn_lookup_or_add_with_vuses (newexpr, tvuses);
@@ -1118,7 +1122,7 @@ phi_translate (tree expr, bitmap_set_t s
return NULL;
oldop0 = find_leader_in_sets (oldop0, set1, set2);
- newop0 = phi_translate (oldop0, set1, set2, pred, phiblock);
+ newop0 = phi_translate (oldop0, set1, set2, pred, phiblock, depth);
if (newop0 == NULL)
return NULL;
@@ -1126,7 +1130,7 @@ phi_translate (tree expr, bitmap_set_t s
{
oldop1 = TREE_OPERAND (expr, 1);
oldop1 = find_leader_in_sets (oldop1, set1, set2);
- newop1 = phi_translate (oldop1, set1, set2, pred, phiblock);
+ newop1 = phi_translate (oldop1, set1, set2, pred, phiblock, depth);
if (newop1 == NULL)
return NULL;
@@ -1135,7 +1139,7 @@ phi_translate (tree expr, bitmap_set_t s
if (oldop2)
{
oldop2 = find_leader_in_sets (oldop2, set1, set2);
- newop2 = phi_translate (oldop2, set1, set2, pred, phiblock);
+ newop2 = phi_translate (oldop2, set1, set2, pred, phiblock, depth);
if (newop2 == NULL)
return NULL;
@@ -1144,7 +1148,7 @@ phi_translate (tree expr, bitmap_set_t s
if (oldop3)
{
oldop3 = find_leader_in_sets (oldop3, set1, set2);
- newop3 = phi_translate (oldop3, set1, set2, pred, phiblock);
+ newop3 = phi_translate (oldop3, set1, set2, pred, phiblock, depth);
if (newop3 == NULL)
return NULL;
@@ -1206,12 +1210,12 @@ phi_translate (tree expr, bitmap_set_t s
tree newexpr;
oldop1 = find_leader_in_sets (oldop1, set1, set2);
- newop1 = phi_translate (oldop1, set1, set2, pred, phiblock);
+ newop1 = phi_translate (oldop1, set1, set2, pred, phiblock, depth);
if (newop1 == NULL)
return NULL;
oldop2 = find_leader_in_sets (oldop2, set1, set2);
- newop2 = phi_translate (oldop2, set1, set2, pred, phiblock);
+ newop2 = phi_translate (oldop2, set1, set2, pred, phiblock, depth);
if (newop2 == NULL)
return NULL;
if (newop1 != oldop1 || newop2 != oldop2)
@@ -1245,7 +1249,7 @@ phi_translate (tree expr, bitmap_set_t s
tree newexpr;
oldop1 = find_leader_in_sets (oldop1, set1, set2);
- newop1 = phi_translate (oldop1, set1, set2, pred, phiblock);
+ newop1 = phi_translate (oldop1, set1, set2, pred, phiblock, depth);
if (newop1 == NULL)
return NULL;
if (newop1 != oldop1)
@@ -1323,7 +1327,7 @@ phi_translate_set (bitmap_set_t dest, bi
for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
{
tree translated;
- translated = phi_translate (expr, set, NULL, pred, phiblock);
+ translated = phi_translate (expr, set, NULL, pred, phiblock, 0);
/* Don't add constants or empty translations to the cache, since
we won't look them up that way, or use the result, anyway. */
@@ -1395,14 +1399,14 @@ value_dies_in_block_x (tree vh, basic_bl
int i;
tree vuse;
VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
-
+
/* Conservatively, a value dies if it's vuses are defined in this
block, unless they come from phi nodes (which are merge operations,
rather than stores. */
for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
{
tree def = SSA_NAME_DEF_STMT (vuse);
-
+
if (bb_for_stmt (def) != block)
continue;
if (TREE_CODE (def) == PHI_NODE)
@@ -1572,7 +1576,7 @@ clean (bitmap_set_t set, basic_block blo
}
static sbitmap has_abnormal_preds;
-
+
/* List of blocks that may have changed during ANTIC computation and
thus need to be iterated over. */
@@ -1679,7 +1683,7 @@ compute_antic_aux (basic_block block, bo
if (phi_nodes (first))
{
bitmap_set_t from = ANTIC_IN (first);
-
+
if (!BB_VISITED (first))
from = maximal_set;
phi_translate_set (ANTIC_OUT, from, block, first);
@@ -1694,22 +1698,22 @@ compute_antic_aux (basic_block block, bo
for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
{
- if (phi_nodes (bprime))
+ if (phi_nodes (bprime))
{
bitmap_set_t tmp = bitmap_set_new ();
bitmap_set_t from = ANTIC_IN (bprime);
-
+
if (!BB_VISITED (bprime))
from = maximal_set;
phi_translate_set (tmp, from, block, bprime);
bitmap_set_and (ANTIC_OUT, tmp);
bitmap_set_free (tmp);
}
- else
+ else
{
if (!BB_VISITED (bprime))
bitmap_set_and (ANTIC_OUT, maximal_set);
- else
+ else
bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
}
}
@@ -2010,7 +2014,7 @@ compute_antic (void)
ANTIC_SAFE_LOADS are those loads generated in a block that actually
occur before any kill to their vuses in the block, and thus, are
safe at the top of the block. This function computes the set by
- walking the EXP_GEN set for the block, and checking the VUSES.
+ walking the EXP_GEN set for the block, and checking the VUSES.
This set could be computed as ANTIC calculation is proceeding, but
but because it does not actually change during that computation, it is
@@ -2023,7 +2027,7 @@ compute_antic_safe (void)
basic_block bb;
bitmap_iterator bi;
unsigned int i;
-
+
FOR_EACH_BB (bb)
{
FOR_EACH_EXPR_ID_IN_SET (EXP_GEN (bb), i, bi)
@@ -2037,26 +2041,28 @@ compute_antic_safe (void)
tree vuse;
tree stmt;
bool okay = true;
-
+
if (!maybe)
continue;
stmt = SSA_NAME_DEF_STMT (maybe);
+ if (TREE_CODE (stmt) == PHI_NODE)
+ continue;
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i,
SSA_OP_VIRTUAL_USES)
- {
+ {
tree def = SSA_NAME_DEF_STMT (vuse);
-
+
if (bb_for_stmt (def) != bb)
continue;
-
+
/* See if the vuse is defined by a statement that
comes before us in the block. Phi nodes are not
stores, so they do not count. */
if (TREE_CODE (def) != PHI_NODE
&& stmt_ann (def)->uid < stmt_ann (stmt)->uid)
{
- okay = false;
+ okay = false;
break;
}
}
@@ -2628,7 +2634,7 @@ do_regular_insertion (basic_block block,
}
bprime = pred->src;
eprime = phi_translate (expr, ANTIC_IN (block), NULL,
- bprime, block);
+ bprime, block, 0);
/* eprime will generally only be NULL if the
value of the expression, translated
@@ -2757,7 +2763,7 @@ do_partial_partial_insertion (basic_bloc
bprime = pred->src;
eprime = phi_translate (expr, ANTIC_IN (block),
PA_IN (block),
- bprime, block);
+ bprime, block, 0);
/* eprime will generally only be NULL if the
value of the expression, translated
@@ -2889,6 +2895,22 @@ is_undefined_value (tree expr)
&& TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
}
+/* Add OP to EXP_GEN (block), and possibly to the maximal set if it is
+ not defined by a phi node.
+ PHI nodes can't go in the maximal sets because they are not in
+ TMP_GEN, so it is possible to get into non-monotonic situations
+ during ANTIC calculation, because it will *add* bits. */
+
+static void
+add_to_exp_gen (basic_block block, tree op)
+{
+
+ bitmap_value_insert_into_set (EXP_GEN (block), op);
+ if (TREE_CODE (op) != SSA_NAME
+ || TREE_CODE (SSA_NAME_DEF_STMT (op)) != PHI_NODE)
+ bitmap_value_insert_into_set (maximal_set, op);
+}
+
/* Given an SSA variable VAR and an expression EXPR, compute the value
number for EXPR and create a value handle (VAL) for it. If VAR and
@@ -2915,11 +2937,6 @@ add_to_sets (tree var, tree expr, tree s
if (s1)
bitmap_insert_into_set (s1, var);
- /* PHI nodes can't go in the maximal sets because they are not in
- TMP_GEN, so it is possible to get into non-monotonic situations
- during ANTIC calculation, because it will *add* bits. */
- if (!in_fre && TREE_CODE (SSA_NAME_DEF_STMT (var)) != PHI_NODE)
- bitmap_value_insert_into_set (maximal_set, var);
bitmap_value_insert_into_set (s2, var);
}
@@ -3015,8 +3032,8 @@ create_value_expr_from (tree expr, basic
val = vn_lookup_or_add (op, NULL);
if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST)
- bitmap_value_insert_into_set (EXP_GEN (block), op);
-
+ add_to_exp_gen (block, op);
+
if (TREE_CODE (val) == VALUE_HANDLE)
TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
@@ -3029,77 +3046,6 @@ create_value_expr_from (tree expr, basic
return vexpr;
}
-/* Given a statement STMT and its right hand side which is a load, try
- to look for the expression stored in the location for the load, and
- return true if a useful equivalence was recorded for LHS. */
-
-static bool
-try_look_through_load (tree lhs, tree mem_ref, tree stmt, basic_block block)
-{
- tree store_stmt = NULL;
- tree rhs;
- ssa_op_iter i;
- tree vuse;
-
- FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
- {
- tree def_stmt;
-
- gcc_assert (TREE_CODE (vuse) == SSA_NAME);
- def_stmt = SSA_NAME_DEF_STMT (vuse);
-
- /* If there is no useful statement for this VUSE, we'll not find a
- useful expression to return either. Likewise, if there is a
- statement but it is not a simple assignment or it has virtual
- uses, we can stop right here. Note that this means we do
- not look through PHI nodes, which is intentional. */
- if (!def_stmt
- || TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT
- || !ZERO_SSA_OPERANDS (def_stmt, SSA_OP_VIRTUAL_USES))
- return false;
-
- /* If this is not the same statement as one we have looked at for
- another VUSE of STMT already, we have two statements producing
- something that reaches our STMT. */
- if (store_stmt && store_stmt != def_stmt)
- return false;
- else
- {
- /* Is this a store to the exact same location as the one we are
- loading from in STMT? */
- if (!operand_equal_p (GIMPLE_STMT_OPERAND (def_stmt, 0), mem_ref, 0))
- return false;
-
- /* Otherwise remember this statement and see if all other VUSEs
- come from the same statement. */
- store_stmt = def_stmt;
- }
- }
-
- /* Alright then, we have visited all VUSEs of STMT and we've determined
- that all of them come from the same statement STORE_STMT. See if there
- is a useful expression we can deduce from STORE_STMT. */
- rhs = GIMPLE_STMT_OPERAND (store_stmt, 1);
- if ((TREE_CODE (rhs) == SSA_NAME
- && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
- || is_gimple_min_invariant (rhs)
- || TREE_CODE (rhs) == ADDR_EXPR
- || TREE_INVARIANT (rhs))
- {
-
- /* Yay! Compute a value number for the RHS of the statement and
- add its value to the AVAIL_OUT set for the block. Add the LHS
- to TMP_GEN. */
- add_to_sets (lhs, rhs, store_stmt, TMP_GEN (block), AVAIL_OUT (block));
- if (TREE_CODE (rhs) == SSA_NAME
- && !is_undefined_value (rhs))
- bitmap_value_insert_into_set (EXP_GEN (block), rhs);
- return true;
- }
-
- return false;
-}
-
/* Return a copy of NODE that is stored in the temporary alloc_pool's.
This is made recursively true, so that the operands are stored in
the pool as well. */
@@ -3274,52 +3220,175 @@ realify_fake_stores (void)
}
}
-/* Tree-combine a value number expression *EXPR_P that does a type
- conversion with the value number expression of its operand.
- Returns true, if *EXPR_P simplifies to a value number or
- gimple min-invariant expression different from EXPR_P and
- sets *EXPR_P to the simplified expression value number.
- Otherwise returns false and does not change *EXPR_P. */
+/* Given an SSA_NAME, see if SCCVN has a value number for it, and if
+ so, return the value handle for this value number, creating it if
+ necessary.
+ Return NULL if SCCVN has no info for us. */
-static bool
-try_combine_conversion (tree *expr_p)
+static tree
+get_sccvn_value (tree name)
{
- tree expr = *expr_p;
- tree t;
- bitmap_set_t exprset;
- unsigned int firstbit;
+ if (TREE_CODE (name) == SSA_NAME
+ && VN_INFO (name)->valnum != name
+ && VN_INFO (name)->valnum != VN_TOP)
+ {
+ tree val = VN_INFO (name)->valnum;
+ bool is_invariant = is_gimple_min_invariant (val);
+ tree valvh = !is_invariant ? get_value_handle (val) : NULL_TREE;
+
+ /* We may end up with situations where SCCVN has chosen a
+ representative for the equivalence set that we have not
+ visited yet. In this case, just create the value handle for
+ it. */
+ if (!valvh && !is_invariant)
+ {
+ gcc_assert (VN_INFO (val)->valnum == val);
+ valvh = vn_lookup_or_add (val, NULL);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "SCCVN says ");
+ print_generic_expr (dump_file, name, 0);
+ fprintf (dump_file, " value numbers to ");
+ if (valvh && !is_invariant)
+ {
+ print_generic_expr (dump_file, val, 0);
+ fprintf (dump_file, " (");
+ print_generic_expr (dump_file, valvh, 0);
+ fprintf (dump_file, ")\n");
+ }
+ else
+ print_generic_stmt (dump_file, val, 0);
+ }
- if (!((TREE_CODE (expr) == NOP_EXPR
- || TREE_CODE (expr) == CONVERT_EXPR
- || TREE_CODE (expr) == REALPART_EXPR
- || TREE_CODE (expr) == IMAGPART_EXPR)
- && TREE_CODE (TREE_OPERAND (expr, 0)) == VALUE_HANDLE
- && !VALUE_HANDLE_VUSES (TREE_OPERAND (expr, 0))))
- return false;
+ if (valvh)
+ return valvh;
+ else
+ return val;
+ }
+ return NULL_TREE;
+}
- exprset = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (expr, 0));
- firstbit = bitmap_first_set_bit (exprset->expressions);
- t = fold_unary (TREE_CODE (expr), TREE_TYPE (expr),
- expression_for_id (firstbit));
- if (!t)
- return false;
+/* Create value handles for PHI in BLOCK. */
+
+static void
+make_values_for_phi (tree phi, basic_block block)
+{
+ tree result = PHI_RESULT (phi);
+ /* We have no need for virtual phis, as they don't represent
+ actual computations. */
+ if (is_gimple_reg (result))
+ {
+ tree sccvnval = get_sccvn_value (result);
+ if (sccvnval)
+ {
+ vn_add (result, sccvnval);
+ bitmap_insert_into_set (PHI_GEN (block), result);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), result);
+ }
+ else
+ add_to_sets (result, result, NULL,
+ PHI_GEN (block), AVAIL_OUT (block));
+ }
+}
- /* Strip useless type conversions, which is safe in the optimizers but
- not generally in fold. */
- STRIP_USELESS_TYPE_CONVERSION (t);
-
- /* Disallow value expressions we have no value number for already, as
- we would miss a leader for it here. */
- if (!(TREE_CODE (t) == VALUE_HANDLE
- || is_gimple_min_invariant (t)))
- t = vn_lookup (t, NULL);
- if (t && t != expr)
+/* Create value handles for STMT in BLOCK. Return true if we handled
+ the statement. */
+
+static bool
+make_values_for_stmt (tree stmt, basic_block block)
+{
+
+ tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ tree valvh = NULL_TREE;
+ tree lhsval;
+
+ valvh = get_sccvn_value (lhs);
+ if (valvh)
{
- *expr_p = t;
+ vn_add (lhs, valvh);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
+ /* Shortcut for FRE. We have no need to create value expressions,
+ just want to know what values are available where. */
+ if (in_fre)
+ return true;
+
+ }
+ else if (in_fre)
+ {
+ /* For FRE, if SCCVN didn't find anything, we aren't going to
+ either, so just make up a new value number. */
+ vn_lookup_or_add (lhs, NULL);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
+ return true;
+ }
+
+ lhsval = valvh ? valvh : get_value_handle (lhs);
+
+ STRIP_USELESS_TYPE_CONVERSION (rhs);
+ if (can_value_number_operation (rhs))
+ {
+ /* For value numberable operation, create a
+ duplicate expression with the operands replaced
+ with the value handles of the original RHS. */
+ tree newt = create_value_expr_from (rhs, block, stmt);
+ if (newt)
+ {
+ /* If we already have a value number for the LHS, reuse
+ it rather than creating a new one. */
+ if (lhsval)
+ {
+ set_value_handle (newt, lhsval);
+ if (!is_gimple_min_invariant (lhsval))
+ add_to_value (lhsval, newt);
+ }
+ else
+ {
+ tree val = vn_lookup_or_add (newt, stmt);
+ vn_add (lhs, val);
+ }
+
+ add_to_exp_gen (block, newt);
+ }
+
+ bitmap_insert_into_set (TMP_GEN (block), lhs);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
+ return true;
+ }
+ else if ((TREE_CODE (rhs) == SSA_NAME
+ && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
+ || is_gimple_min_invariant (rhs)
+ || TREE_CODE (rhs) == ADDR_EXPR
+ || TREE_INVARIANT (rhs)
+ || DECL_P (rhs))
+ {
+
+ if (lhsval)
+ {
+ set_value_handle (rhs, lhsval);
+ if (!is_gimple_min_invariant (lhsval))
+ add_to_value (lhsval, rhs);
+ bitmap_insert_into_set (TMP_GEN (block), lhs);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
+ }
+ else
+ {
+ /* Compute a value number for the RHS of the statement
+ and add its value to the AVAIL_OUT set for the block.
+ Add the LHS to TMP_GEN. */
+ add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
+ AVAIL_OUT (block));
+ }
+ /* None of the rest of these can be PRE'd. */
+ if (TREE_CODE (rhs) == SSA_NAME && !is_undefined_value (rhs))
+ add_to_exp_gen (block, rhs);
return true;
}
return false;
+
}
/* Compute the AVAIL set for all basic blocks.
@@ -3339,6 +3408,7 @@ compute_avail (void)
basic_block *worklist;
size_t sp = 0;
tree param;
+
/* For arguments with default definitions, we pretend they are
defined in the entry block. */
for (param = DECL_ARGUMENTS (current_function_decl);
@@ -3350,9 +3420,11 @@ compute_avail (void)
tree def = gimple_default_def (cfun, param);
vn_lookup_or_add (def, NULL);
- bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
if (!in_fre)
- bitmap_value_insert_into_set (maximal_set, def);
+ {
+ bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
+ bitmap_value_insert_into_set (maximal_set, def);
+ }
bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
}
}
@@ -3366,9 +3438,11 @@ compute_avail (void)
tree def = gimple_default_def (cfun, param);
vn_lookup_or_add (def, NULL);
- bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
- if (!in_fre)
- bitmap_value_insert_into_set (maximal_set, def);
+ if (!in_fre)
+ {
+ bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
+ bitmap_value_insert_into_set (maximal_set, def);
+ }
bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
}
}
@@ -3402,15 +3476,7 @@ compute_avail (void)
/* Generate values for PHI nodes. */
for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
- {
- /* We have no need for virtual phis, as they don't represent
- actual computations. */
- if (is_gimple_reg (PHI_RESULT (phi)))
- {
- add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
- PHI_GEN (block), AVAIL_OUT (block));
- }
- }
+ make_values_for_phi (phi, block);
/* Now compute value numbers and populate value sets with all
the expressions computed in BLOCK. */
@@ -3439,11 +3505,27 @@ compute_avail (void)
stmt = TREE_OPERAND (stmt, 0);
if (stmt && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
{
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ if (TREE_CODE (lhs) == SSA_NAME
+ && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "SCCVN says ");
+ print_generic_expr (dump_file, lhs, 0);
+ fprintf (dump_file, " value numbers to ");
+ print_generic_stmt (dump_file, VN_INFO (lhs)->valnum,
+ 0);
+ }
+ vn_add (lhs, VN_INFO (lhs)->valnum);
+ continue;
+ }
+
if (TREE_CODE (rhs) == SSA_NAME
- && !is_undefined_value (rhs))
- bitmap_value_insert_into_set (EXP_GEN (block), rhs);
+ && !is_undefined_value (rhs)
+ && !in_fre)
+ add_to_exp_gen (block, rhs);
FOR_EACH_SSA_TREE_OPERAND (op, realstmt, iter, SSA_OP_DEF)
add_to_sets (op, op, NULL, TMP_GEN (block),
@@ -3456,62 +3538,11 @@ compute_avail (void)
&& !ann->has_volatile_ops
&& TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
- (GIMPLE_STMT_OPERAND (stmt, 0)))
+ (GIMPLE_STMT_OPERAND (stmt, 0)))
{
- tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
- tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
-
- /* Try to look through loads. */
- if (TREE_CODE (lhs) == SSA_NAME
- && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES)
- && try_look_through_load (lhs, rhs, stmt, block))
+ if (make_values_for_stmt (stmt, block))
continue;
- STRIP_USELESS_TYPE_CONVERSION (rhs);
- if (can_value_number_operation (rhs))
- {
- /* For value numberable operation, create a
- duplicate expression with the operands replaced
- with the value handles of the original RHS. */
- tree newt = create_value_expr_from (rhs, block, stmt);
- if (newt)
- {
- /* If we can combine a conversion expression
- with the expression for its operand just
- record the value number for it. */
- if (try_combine_conversion (&newt))
- vn_add (lhs, newt);
- else
- {
- tree val = vn_lookup_or_add (newt, stmt);
- vn_add (lhs, val);
- if (!in_fre)
- bitmap_value_insert_into_set (maximal_set, newt);
- bitmap_value_insert_into_set (EXP_GEN (block), newt);
- }
- bitmap_insert_into_set (TMP_GEN (block), lhs);
- bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
- continue;
- }
- }
- else if ((TREE_CODE (rhs) == SSA_NAME
- && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
- || is_gimple_min_invariant (rhs)
- || TREE_CODE (rhs) == ADDR_EXPR
- || TREE_INVARIANT (rhs)
- || DECL_P (rhs))
- {
- /* Compute a value number for the RHS of the statement
- and add its value to the AVAIL_OUT set for the block.
- Add the LHS to TMP_GEN. */
- add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
- AVAIL_OUT (block));
-
- if (TREE_CODE (rhs) == SSA_NAME
- && !is_undefined_value (rhs))
- bitmap_value_insert_into_set (EXP_GEN (block), rhs);
- continue;
- }
}
/* For any other statement that we don't recognize, simply
@@ -3521,7 +3552,12 @@ compute_avail (void)
add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
- add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
+ {
+ add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
+ if (!in_fre
+ && (TREE_CODE (op) == SSA_NAME || can_PRE_operation (op)))
+ add_to_exp_gen (block, op);
+ }
}
/* Put the dominator children of BLOCK on the worklist of blocks
@@ -3685,14 +3721,14 @@ remove_dead_inserted_code (void)
else
{
/* Propagate through the operands. Examine all the USE, VUSE and
- VDEF operands in this statement. Mark all the statements
+ VDEF operands in this statement. Mark all the statements
which feed this statement's uses as necessary. */
ssa_op_iter iter;
tree use;
/* The operands of VDEF expressions are also needed as they
represent potential definitions that may reach this
- statement (VDEF operands allow us to follow def-def
+ statement (VDEF operands allow us to follow def-def
links). */
FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
@@ -3781,7 +3817,7 @@ init_pre (bool do_fre)
tree_code_size (EQ_EXPR), 30);
modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
tree_code_size (GIMPLE_MODIFY_STMT),
- 30);
+ 30);
obstack_init (&temp_call_expr_obstack);
modify_expr_template = NULL;
@@ -3867,7 +3903,9 @@ execute_pre (bool do_fre)
insert_fake_stores ();
/* Collect and value number expressions computed in each basic block. */
+ run_scc_vn ();
compute_avail ();
+ free_scc_vn ();
if (dump_file && (dump_flags & TDF_DETAILS))
{