This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Implement load PRE
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 30 Dec 2005 13:02:06 -0500
- Subject: [PATCH]: Implement load PRE
This patch implements load PRE at the tree level.
Only expressions of the form INDIRECT_REF<name> are handled ATM. This
isn't really a technical problem, it's because the portion that
recreates expressions does it in pieces, and it's not legal to generate
GIMPLE of the form "pretmp_3" where pretmp is an aggregate type.
IE, it would attempt to generate things like a->b as
pretemp_3 = *a
pretemp_4 = pretemp_3.b
and we don't allow that.
I will fix this soon by rewriting it to understand how to generate
COMPONENT_REF of INDIRECT_REF properly.
The patch consists of three main portions:
1. Changing value numbering to take a vector of vuses, instead of the
statement, so that we can compare vuses on created expressions properly
during phi translation.
2. Adding some dataflow to determine where loads reach. This requires
determining what names virtual uses actually represent, because we can't
generate virtual uses with overlapping lifetimes. We could simply kill
all names merged at a phi, but we get better results if we just keep a
bitmap of what names the merged name represents, and then only kill
those names when the phi value is actually def'd.
3. Inserting fake temporaries for each store, value numbering them, and
then making them real if we turn out to use them. This avoids trying to
figure out where we need to reload values due to stores. You can
actually avoid this step entirely, you just get less loads moved around
because we think they die more than they actually do. We could also
just mark locations we could insert the reloads, pretend they already
exist, and then make them exist if necessary. This is tricky. SSAPRE
used to just insert at every kill point as well, like we do.
Theoretically, #2 and #3 could be done sparsely, but it's not clear
whether it is worth it.
If it's worth it anywhere, it's probably #3.
However, to cut down on memory usage due to inserting fake temporaries
for store, we pool allocate the entire expression, and then if we end up
using it, we then gc allocate it.
This patch adds about 1% compile time, but it's due to the extra
may-alias pass, *not* the actual PRE. I can probably make this go away
with a little work on teaching it to use the vuses, since we know what
vuses the expression will get (the real problem with this is that we
won't get name tags for the pretemp's, so eventually *something* has to
rerun aliasing, or we have to be able to tell the aliaser to figure out
what these new things point to)
Bootstrapped and regtested on i686-pc-linux-gnu and powerpc-linux-gnu,
and committed to mainline.
--Dan
2005-12-29 Daniel Berlin <dberlin@dberlin.org>
* tree.h (VALUE_HANDLE_VUSES): New.
(struct tree_value_handle): Add vuses.
* tree-vn.c (struct val_expr_pair_d): Remove stmt, add vuses.
(vn_compute): Remove stmt argument.
Don't use vuses in hash value computation.
(val_expr_pair_eq): Compare vuse lists.
(copy_vuses_from_stmt): New function.
(shared_vuses_from_stmt): Ditto.
(vn_add): Rewrite in terms of vn_add_with_vuses.
(vn_add_with_vuses): New function.
(vn_lookup): Rewrite in terms of vn_lookup_with_vuses.
(vn_lookup_with_vuses): New function.
(vuses_compare): New function.
(print_creation_to_file): Ditto.
(vn_lookup_or_add): Rewrite to handle vuses.
(sort_vuses): New function.
(vn_lookup_or_add_with_vuses): Ditto.
(vn_init): Initialize shared_lookup_vuses.
(vn_delete): Free shared_lookup_vuses.
* tree-ssa-pre.c: Update todo list.
(bb_value_sets_t): Add rvuse_in, rvuse_out, rvuse_gen, and
rvuse_kill.
(RVUSE_IN): New macro.
(RVUSE_GEN): Ditto.
(RVUSE_KILL): Ditto.
(RVUSE_OUT): Ditto.
(modify_expr_node_pool): New function.
(pretemp): New.
(storetemp): Ditto.
(mergephitemp): Ditto.
(prephitemp): Ditto.
(struct expr_pred_trans_d): Add vuses member.
(expr_pred_trans_eq): Compare vuses.
(phi_trans_lookup): Add vuses argument.
(phi_trans_add): Ditto.
(translate_vuses_through_block): New function.
(phi_translate): Use vuses to ask about those expressions that can
have vuses.
Properly translate virtual uses through phis, and use
vn_lookup_or_add_with vuses. Handle tcc_reference.
(phi_translate_set): Don't add pointless translations to the
cache.
(get_representative): New function.
(vuses_dies_in_block_x): Ditto.
(valid_in_set): Add block argument. Check virtual use validity.
(clean): Add block argument. Update call to valid_in_set
(compute_antic_aux): Update call to clean.
(dump_bitmap_of_names): New function.
(compute_vuse_representatives): Ditto.
(compute_rvuse): Ditto.
(can_value_number_call): Modified to accept calls with vuses.
(can_value_number_operation): New function.
(can_PRE_operation): Ditto.
(need_creation): New vector of stores that may need creation.
(find_or_generate_expression): use can_PRE_operation.
(create_expression_by_pieces): Handle INDIRECT_REF.
Only create one temp until we have to change types.
Mark new vars for renaming.
(insert_into_preds_of_block): Ignore loopiness of loads.
Use can_PRE_operation.
Only create one temp until we have to chnge types.
(insert_aux): Use can_PRE_operation.
Don't pass name to insert_into_preds_of_block.
(insert_extra_phis): Only use one temp until we have to change
types.
(poolify_tree): New function.
(modify_expr_template): New var.
(poolify_modify_expr): New function.
(insert_fake_stores): Ditto.
(realify_fake_stores): Ditto.
(compute_avail): Use can_value_number_operation.
(mark_operand_necessary): Return NULL for non-SSA names.
(remove_dead_inserted_code): Update comment.
(init_pre): Initialize pretemp, need_creation, storetemp,
mergephitemp, prephitemp.
Create modify_expr_node_pool.
(fini_pre): Free modify_expr_node_pool and need_creation array.
(execute_pre): Call insert_fake_stores, compute_rvuse, and
realify_fake_stores.
* tree-flow.h (vn_compute): Fix prototype.
(vn_add): Ditto.
(vn_lookup): Ditto.
(sort_vuses): New.
(vn_lookup_or_add_with_vuses): Ditto.
(vn_add_with_vuses): Ditto.
(vn_lookup_with_vuses): Ditto.
* passes.c (pass_may_alias): Add.
Index: tree.h
===================================================================
--- tree.h (revision 109165)
+++ tree.h (working copy)
@@ -2814,6 +2814,9 @@ struct tree_statement_list
#define VALUE_HANDLE_EXPR_SET(NODE) \
(VALUE_HANDLE_CHECK (NODE)->value_handle.expr_set)
+#define VALUE_HANDLE_VUSES(NODE) \
+ (VALUE_HANDLE_CHECK (NODE)->value_handle.vuses)
+
/* Defined and used in tree-ssa-pre.c. */
struct value_set;
@@ -2828,6 +2831,9 @@ struct tree_value_handle GTY(())
conveniently dense form starting at 0, so that we can make
bitmaps of value handles. */
unsigned int id;
+
+ /* Set of virtual uses represented by this handle. */
+ VEC (tree, gc) *vuses;
};
/* Define the overall contents of a tree node.
Index: tree-vn.c
===================================================================
--- tree-vn.c (revision 109165)
+++ tree-vn.c (working copy)
@@ -48,8 +48,8 @@ typedef struct val_expr_pair_d
/* Associated expression. */
tree e;
- /* for comparing Virtual uses in E. */
- tree stmt;
+ /* For comparing virtual uses in E. */
+ VEC (tree, gc) *vuses;
/* E's hash value. */
hashval_t hashcode;
@@ -77,16 +77,11 @@ make_value_handle (tree type)
any).
VAL can be used to iterate by passing previous value numbers (it is
- used by iterative_hash_expr).
-
- STMT is the stmt associated with EXPR for comparing virtual operands. */
+ used by iterative_hash_expr). */
hashval_t
-vn_compute (tree expr, hashval_t val, tree stmt)
+vn_compute (tree expr, hashval_t val)
{
- ssa_op_iter iter;
- tree vuse;
-
/* EXPR must not be a statement. We are only interested in value
numbering expressions on the RHS of assignments. */
gcc_assert (expr);
@@ -94,17 +89,9 @@ vn_compute (tree expr, hashval_t val, tr
|| expr->common.ann->common.type != STMT_ANN);
val = iterative_hash_expr (expr, val);
-
- /* If the expression has virtual uses, incorporate them into the
- hash value computed for EXPR. */
- if (stmt)
- FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
- val = iterative_hash_expr (vuse, val);
-
return val;
}
-
/* Compare two expressions E1 and E2 and return true if they are
equal. */
@@ -163,15 +150,26 @@ val_expr_pair_hash (const void *p)
static int
val_expr_pair_expr_eq (const void *p1, const void *p2)
{
- bool ret;
+ int i;
+ tree vuse1;
const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
if (! expressions_equal_p (ve1->e, ve2->e))
return false;
- ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE);
- return ret;
+ if (ve1->vuses == ve2->vuses)
+ return true;
+
+ if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
+ return false;
+
+ for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
+ {
+ if (VEC_index (tree, ve2->vuses, i) != vuse1)
+ return false;
+ }
+ return true;
}
@@ -190,13 +188,68 @@ set_value_handle (tree e, tree v)
gcc_assert (is_gimple_min_invariant (e));
}
+/* Copy the virtual uses from STMT into a newly allocated VEC(tree),
+ and return the VEC(tree). */
+
+static VEC (tree, gc) *
+copy_vuses_from_stmt (tree stmt)
+{
+ ssa_op_iter iter;
+ tree vuse;
+ VEC (tree, gc) *vuses = NULL;
+
+ if (!stmt)
+ return NULL;
+
+ FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
+ VEC_safe_push (tree, gc, vuses, vuse);
+
+ return vuses;
+}
+
+/* Place for shared_vuses_from_stmt to shove vuses. */
+static VEC (tree, gc) *shared_lookup_vuses;
+
+/* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
+ This function will overwrite the current SHARED_LOOKUP_VUSES
+ variable. */
+
+static VEC (tree, gc) *
+shared_vuses_from_stmt (tree stmt)
+{
+ ssa_op_iter iter;
+ tree vuse;
+
+ if (!stmt)
+ return NULL;
+
+ VEC_truncate (tree, shared_lookup_vuses, 0);
+
+ FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
+ VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
+
+ if (VEC_length (tree, shared_lookup_vuses) > 1)
+ sort_vuses (shared_lookup_vuses);
+
+ return shared_lookup_vuses;
+}
+
+/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
+ EXPR to the value set for value VAL. */
+
+void
+vn_add (tree expr, tree val)
+{
+ vn_add_with_vuses (expr, val, NULL);
+}
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
- EXPR to the value set for value VAL. STMT represents the stmt
- associated with EXPR. It is used when computing a hash value for EXPR. */
+ EXPR to the value set for value VAL. VUSES represents the virtual
+ use operands associated with EXPR. It is used when computing a
+ hash value for EXPR. */
void
-vn_add (tree expr, tree val, tree stmt)
+vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
{
void **slot;
val_expr_pair_t new_pair;
@@ -204,8 +257,8 @@ vn_add (tree expr, tree val, tree stmt)
new_pair = XNEW (struct val_expr_pair_d);
new_pair->e = expr;
new_pair->v = val;
- new_pair->stmt = stmt;
- new_pair->hashcode = vn_compute (expr, 0, stmt);
+ new_pair->vuses = vuses;
+ new_pair->hashcode = vn_compute (expr, 0);
slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
INSERT);
if (*slot)
@@ -213,7 +266,8 @@ vn_add (tree expr, tree val, tree stmt)
*slot = (void *) new_pair;
set_value_handle (expr, val);
- add_to_value (val, expr);
+ if (TREE_CODE (val) == VALUE_HANDLE)
+ add_to_value (val, expr);
}
@@ -225,6 +279,17 @@ vn_add (tree expr, tree val, tree stmt)
tree
vn_lookup (tree expr, tree stmt)
{
+ return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
+}
+
+/* Search in VALUE_TABLE for an existing instance of expression EXPR,
+ and return its value, or NULL if none has been set. VUSES is the
+ list of virtual use operands associated with EXPR. It is used when
+ computing the hash value for EXPR. */
+
+tree
+vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
+{
void **slot;
struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
@@ -233,8 +298,8 @@ vn_lookup (tree expr, tree stmt)
return expr;
vep.e = expr;
- vep.stmt = stmt;
- vep.hashcode = vn_compute (expr, 0, stmt);
+ vep.vuses = vuses;
+ vep.hashcode = vn_compute (expr, 0);
slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
if (!slot)
return NULL_TREE;
@@ -243,10 +308,53 @@ vn_lookup (tree expr, tree stmt)
}
+/* A comparison function for use in qsort to compare vuses. Simply
+ subtracts version numbers. */
+
+static int
+vuses_compare (const void *pa, const void *pb)
+{
+ const tree vusea = *((const tree *)pa);
+ const tree vuseb = *((const tree *)pb);
+ int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
+
+ return sn;
+}
+
+/* Print out the "Created value <x> for <Y>" statement to the
+ dump_file.
+ This is factored because both versions of lookup use it, and it
+ obscures the real work going on in those functions. */
+
+static void
+print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
+{
+ fprintf (dump_file, "Created value ");
+ print_generic_expr (dump_file, v, dump_flags);
+ fprintf (dump_file, " for ");
+ print_generic_expr (dump_file, expr, dump_flags);
+
+ if (vuses && VEC_length (tree, vuses) != 0)
+ {
+ size_t i;
+ tree vuse;
+
+ fprintf (dump_file, " vuses: (");
+ for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
+ {
+ print_generic_expr (dump_file, vuse, dump_flags);
+ if (VEC_length (tree, vuses) - 1 != i)
+ fprintf (dump_file, ",");
+ }
+ fprintf (dump_file, ")");
+ }
+ fprintf (dump_file, "\n");
+}
+
/* 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
- when computing the hash value for EXPR. */
+ value for EXPR. STMT represents the stmt associated with EXPR. It
+ is used when computing the VUSES for EXPR. */
tree
vn_lookup_or_add (tree expr, tree stmt)
@@ -254,18 +362,17 @@ vn_lookup_or_add (tree expr, tree stmt)
tree v = vn_lookup (expr, stmt);
if (v == NULL_TREE)
{
+ VEC(tree,gc) *vuses;
+
v = make_value_handle (TREE_TYPE (expr));
+ vuses = copy_vuses_from_stmt (stmt);
+ sort_vuses (vuses);
if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Created value ");
- print_generic_expr (dump_file, v, dump_flags);
- fprintf (dump_file, " for ");
- print_generic_expr (dump_file, expr, dump_flags);
- fprintf (dump_file, "\n");
- }
+ print_creation_to_file (v, expr, vuses);
- vn_add (expr, v, stmt);
+ VALUE_HANDLE_VUSES (v) = vuses;
+ vn_add_with_vuses (expr, v, vuses);
}
set_value_handle (expr, v);
@@ -273,6 +380,46 @@ vn_lookup_or_add (tree expr, tree stmt)
return v;
}
+/* Sort the VUSE array so that we can do equality comparisons
+ quicker on two vuse vecs. */
+
+void
+sort_vuses (VEC (tree,gc) *vuses)
+{
+ if (VEC_length (tree, vuses) > 1)
+ qsort (VEC_address (tree, vuses),
+ VEC_length (tree, vuses),
+ sizeof (tree),
+ vuses_compare);
+}
+
+/* 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
+ when computing the hash value for EXPR. */
+
+tree
+vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
+{
+ tree v = vn_lookup_with_vuses (expr, vuses);
+ if (v == NULL_TREE)
+ {
+ v = make_value_handle (TREE_TYPE (expr));
+ sort_vuses (vuses);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ print_creation_to_file (v, expr, vuses);
+
+ VALUE_HANDLE_VUSES (v) = vuses;
+ vn_add_with_vuses (expr, v, vuses);
+ }
+
+ set_value_handle (expr, v);
+
+ return v;
+}
+
+
/* Get the value handle of EXPR. This is the only correct way to get
the value handle for a "thing". If EXPR does not have a value
@@ -306,6 +453,7 @@ vn_init (void)
{
value_table = htab_create (511, val_expr_pair_hash,
val_expr_pair_expr_eq, free);
+ shared_lookup_vuses = NULL;
}
@@ -315,5 +463,6 @@ void
vn_delete (void)
{
htab_delete (value_table);
+ VEC_free (tree, gc, shared_lookup_vuses);
value_table = NULL;
}
Index: tree-ssa-pre.c
===================================================================
--- tree-ssa-pre.c (revision 109165)
+++ tree-ssa-pre.c (working copy)
@@ -49,13 +49,9 @@ Boston, MA 02110-1301, USA. */
1. Avail sets can be shared by making an avail_find_leader that
walks up the dominator tree and looks in those avail sets.
This might affect code optimality, it's unclear right now.
- 2. Load motion can be performed by value numbering the loads the
- same as we do other expressions. This requires iterative
- hashing the vuses into the values. Right now we simply assign
- a new value every time we see a statement with a vuse.
- 3. Strength reduction can be performed by anticipating expressions
+ 2. Strength reduction can be performed by anticipating expressions
we can repair later on.
- 4. We can do back-substitution or smarter value numbering to catch
+ 3. We can do back-substitution or smarter value numbering to catch
commutative expressions split up over multiple statements.
*/
@@ -247,7 +243,7 @@ typedef struct bb_value_sets
a given basic block. */
bitmap_set_t avail_out;
- /* The ANTIC_IN set, which represents which values are anticiptable
+ /* The ANTIC_IN set, which represents which values are anticipatable
in a given basic block. */
value_set_t antic_in;
@@ -255,6 +251,13 @@ typedef struct bb_value_sets
AVAIL_OUT set of blocks with the new insertions performed during
the current iteration. */
bitmap_set_t new_sets;
+
+ /* The RVUSE sets, which are used during ANTIC computation to ensure
+ that we don't mark loads ANTIC once they have died. */
+ bitmap rvuse_in;
+ bitmap rvuse_out;
+ bitmap rvuse_gen;
+ bitmap rvuse_kill;
} *bb_value_sets_t;
#define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
@@ -262,6 +265,10 @@ typedef struct bb_value_sets
#define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
#define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
#define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
+#define RVUSE_IN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_in
+#define RVUSE_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_gen
+#define RVUSE_KILL(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_kill
+#define RVUSE_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->rvuse_out
#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
/* This structure is used to keep track of statistics on what
@@ -309,8 +316,18 @@ static alloc_pool reference_node_pool;
static alloc_pool comparison_node_pool;
static alloc_pool expression_node_pool;
static alloc_pool list_node_pool;
+static alloc_pool modify_expr_node_pool;
static bitmap_obstack grand_bitmap_obstack;
+/* To avoid adding 300 temporary variables when we only need one, we
+ only create one temporary variable, on demand, and build ssa names
+ off that. We do have to change the variable if the types don't
+ match the current variable's type. */
+static tree pretemp;
+static tree storetemp;
+static tree mergephitemp;
+static tree prephitemp;
+
/* Set of blocks with statements that have had its EH information
cleaned up. */
static bitmap need_eh_cleanup;
@@ -331,9 +348,13 @@ typedef struct expr_pred_trans_d
/* The predecessor block along which we translated the expression. */
basic_block pred;
+ /* vuses associated with the expression. */
+ VEC (tree, gc) *vuses;
+
/* The value that resulted from the translation. */
tree v;
+
/* The hashcode for the expression, pred pair. This is cached for
speed reasons. */
hashval_t hashcode;
@@ -358,33 +379,50 @@ expr_pred_trans_eq (const void *p1, cons
const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
basic_block b1 = ve1->pred;
basic_block b2 = ve2->pred;
-
+ int i;
+ tree vuse1;
/* If they are not translations for the same basic block, they can't
be equal. */
if (b1 != b2)
return false;
+
/* If they are for the same basic block, determine if the
expressions are equal. */
- if (expressions_equal_p (ve1->e, ve2->e))
+ if (!expressions_equal_p (ve1->e, ve2->e))
+ return false;
+
+ /* Make sure the vuses are equivalent. */
+ if (ve1->vuses == ve2->vuses)
return true;
- return false;
+ if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
+ return false;
+
+ for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
+ {
+ if (VEC_index (tree, ve2->vuses, i) != vuse1)
+ return false;
+ }
+
+ return true;
}
/* Search in the phi translation table for the translation of
- expression E in basic block PRED. Return the translated value, if
- found, NULL otherwise. */
+ expression E in basic block PRED with vuses VUSES.
+ Return the translated value, if found, NULL otherwise. */
static inline tree
-phi_trans_lookup (tree e, basic_block pred)
+phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses)
{
void **slot;
struct expr_pred_trans_d ept;
+
ept.e = e;
ept.pred = pred;
- ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
+ ept.vuses = vuses;
+ ept.hashcode = vn_compute (e, (unsigned long) pred);
slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
NO_INSERT);
if (!slot)
@@ -394,18 +432,19 @@ phi_trans_lookup (tree e, basic_block pr
}
-/* Add the tuple mapping from {expression E, basic block PRED} to
+/* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
value V, to the phi translation table. */
static inline void
-phi_trans_add (tree e, tree v, basic_block pred)
+phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses)
{
void **slot;
expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
new_pair->e = e;
new_pair->pred = pred;
+ new_pair->vuses = vuses;
new_pair->v = v;
- new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
+ new_pair->hashcode = vn_compute (e, (unsigned long) pred);
slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
new_pair->hashcode, INSERT);
if (*slot)
@@ -936,7 +975,42 @@ pool_copy_list (tree list)
return head;
}
+/* Translate the vuses in the VUSES vector backwards through phi
+ nodes, so that they have the value they would have in BLOCK. */
+
+static VEC(tree, gc) *
+translate_vuses_through_block (VEC (tree, gc) *vuses, basic_block block)
+{
+ tree oldvuse;
+ VEC(tree, gc) *result = NULL;
+ int i;
+ for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
+ {
+ tree phi = SSA_NAME_DEF_STMT (oldvuse);
+ if (TREE_CODE (phi) == PHI_NODE)
+ {
+ edge e = find_edge (block, bb_for_stmt (phi));
+ if (e)
+ {
+ tree def = PHI_ARG_DEF (phi, e->dest_idx);
+ if (def != oldvuse)
+ {
+ if (!result)
+ result = VEC_copy (tree, gc, vuses);
+ VEC_replace (tree, result, i, def);
+ }
+ }
+ }
+ }
+ if (result)
+ {
+ sort_vuses (result);
+ return result;
+ }
+ return vuses;
+
+}
/* Translate EXPR using phis in PHIBLOCK, so that it has the values of
the phis in PRED. Return NULL if we can't find a leader for each
part of the translated expression. */
@@ -947,7 +1021,6 @@ phi_translate (tree expr, value_set_t se
{
tree phitrans = NULL;
tree oldexpr = expr;
-
if (expr == NULL)
return NULL;
@@ -955,7 +1028,19 @@ phi_translate (tree expr, value_set_t se
return expr;
/* Phi translations of a given expression don't change. */
- phitrans = phi_trans_lookup (expr, pred);
+ if (EXPR_P (expr))
+ {
+ tree vh;
+
+ vh = get_value_handle (expr);
+ if (vh && TREE_CODE (vh) == VALUE_HANDLE)
+ phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh));
+ else
+ phitrans = phi_trans_lookup (expr, pred, NULL);
+ }
+ else
+ phitrans = phi_trans_lookup (expr, pred, NULL);
+
if (phitrans)
return phitrans;
@@ -976,7 +1061,10 @@ phi_translate (tree expr, value_set_t se
tree oldwalker;
tree newwalker;
tree newexpr;
+ tree vh = get_value_handle (expr);
bool listchanged = false;
+ VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
+ VEC (tree, gc) *tvuses;
/* Call expressions are kind of weird because they have an
argument list. We don't want to value number the list
@@ -1028,7 +1116,10 @@ phi_translate (tree expr, value_set_t se
if (listchanged)
vn_lookup_or_add (newarglist, NULL);
- if (listchanged || (newop0 != oldop0) || (oldop2 != newop2))
+ tvuses = translate_vuses_through_block (vuses, pred);
+
+ if (listchanged || (newop0 != oldop0) || (oldop2 != newop2)
+ || vuses != tvuses)
{
newexpr = (tree) pool_alloc (expression_node_pool);
memcpy (newexpr, expr, tree_size (expr));
@@ -1036,17 +1127,76 @@ phi_translate (tree expr, value_set_t se
TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist;
TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
create_tree_ann (newexpr);
- vn_lookup_or_add (newexpr, NULL);
+ vn_lookup_or_add_with_vuses (newexpr, tvuses);
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred);
+ phi_trans_add (oldexpr, newexpr, pred, tvuses);
}
}
}
return expr;
+ case tcc_declaration:
+ {
+ VEC (tree, gc) * oldvuses = NULL;
+ VEC (tree, gc) * newvuses = NULL;
+
+ oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
+ if (oldvuses)
+ newvuses = translate_vuses_through_block (oldvuses, pred);
+
+ if (oldvuses != newvuses)
+ vn_lookup_or_add_with_vuses (expr, newvuses);
+
+ phi_trans_add (oldexpr, expr, pred, newvuses);
+ }
+ return expr;
+
case tcc_reference:
- /* XXX: Until we have PRE of loads working, none will be ANTIC. */
- return NULL;
+ {
+ tree oldop1 = TREE_OPERAND (expr, 0);
+ tree newop1;
+ tree newexpr;
+ VEC (tree, gc) * oldvuses = NULL;
+ VEC (tree, gc) * newvuses = NULL;
+
+ if (TREE_CODE (expr) != INDIRECT_REF)
+ return NULL;
+
+ newop1 = phi_translate (find_leader (set, oldop1),
+ set, pred, phiblock);
+ if (newop1 == NULL)
+ return NULL;
+
+ oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
+ if (oldvuses)
+ newvuses = translate_vuses_through_block (oldvuses, pred);
+
+ if (newop1 != oldop1 || newvuses != oldvuses)
+ {
+ tree t;
+
+ newexpr = pool_alloc (reference_node_pool);
+ memcpy (newexpr, expr, tree_size (expr));
+ TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
+
+ t = fully_constant_expression (newexpr);
+
+ if (t != newexpr)
+ {
+ pool_free (reference_node_pool, newexpr);
+ newexpr = t;
+ }
+ else
+ {
+ create_tree_ann (newexpr);
+ vn_lookup_or_add_with_vuses (newexpr, newvuses);
+ }
+ expr = newexpr;
+ phi_trans_add (oldexpr, newexpr, pred, newvuses);
+ }
+ }
+ return expr;
+ break;
case tcc_binary:
case tcc_comparison:
@@ -1084,7 +1234,7 @@ phi_translate (tree expr, value_set_t se
vn_lookup_or_add (newexpr, NULL);
}
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred);
+ phi_trans_add (oldexpr, newexpr, pred, NULL);
}
}
return expr;
@@ -1117,7 +1267,7 @@ phi_translate (tree expr, value_set_t se
vn_lookup_or_add (newexpr, NULL);
}
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred);
+ phi_trans_add (oldexpr, newexpr, pred, NULL);
}
}
return expr;
@@ -1162,9 +1312,23 @@ phi_translate_set (value_set_t dest, val
node = node->next)
{
tree translated;
- translated = phi_translate (node->expr, set, pred, phiblock);
- phi_trans_add (node->expr, translated, pred);
+ translated = phi_translate (node->expr, set, pred, phiblock);
+
+ /* Don't add constants or empty translations to the cache, since
+ we won't look them up that way, or use the result, anyway. */
+ if (translated && !is_gimple_min_invariant (translated))
+ {
+ tree vh = get_value_handle (translated);
+ VEC (tree, gc) *vuses;
+
+ /* The value handle itself may also be an invariant, in
+ which case, it has no vuses. */
+ vuses = !is_gimple_min_invariant (vh)
+ ? VALUE_HANDLE_VUSES (vh) : NULL;
+ phi_trans_add (node->expr, translated, pred, vuses);
+ }
+
if (translated != NULL)
value_insert_into_set (dest, translated);
}
@@ -1245,6 +1409,42 @@ find_leader (value_set_t set, tree val)
return NULL;
}
+/* Given the vuse representative map, MAP, and an SSA version number,
+ ID, return the bitmap of names ID represents, or NULL, if none
+ exists. */
+
+static bitmap
+get_representative (bitmap *map, int id)
+{
+ if (map[id] != NULL)
+ return map[id];
+ return NULL;
+}
+
+/* A vuse is anticipable at the top of block x, from the bottom of the
+ block, if it reaches the top of the block, and is not killed in the
+ block. In effect, we are trying to see if the vuse is transparent
+ backwards in the block. */
+
+static bool
+vuses_dies_in_block_x (VEC (tree, gc) *vuses, basic_block block)
+{
+ int i;
+ tree vuse;
+
+ for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
+ {
+ /* Any places where this is too conservative, are places
+ where we created a new version and shouldn't have. */
+
+ if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse))
+ || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION
+ (vuse)))
+ return true;
+ }
+ return false;
+}
+
/* Determine if the expression EXPR is valid in SET. This means that
we have a leader for each part of the expression (if it consists of
values), or the expression is an SSA_NAME.
@@ -1255,9 +1455,10 @@ find_leader (value_set_t set, tree val)
(IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
static bool
-valid_in_set (value_set_t set, tree expr)
+valid_in_set (value_set_t set, tree expr, basic_block block)
{
- switch (TREE_CODE_CLASS (TREE_CODE (expr)))
+ tree vh = get_value_handle (expr);
+ switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_binary:
case tcc_comparison:
@@ -1292,13 +1493,27 @@ valid_in_set (value_set_t set, tree expr
if (!set_contains_value (set, TREE_VALUE (arglist)))
return false;
}
- return true;
+ return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
}
return false;
}
case tcc_reference:
- /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
+ {
+ if (TREE_CODE (expr) == INDIRECT_REF)
+ {
+ tree op0 = TREE_OPERAND (expr, 0);
+ if (is_gimple_min_invariant (op0)
+ || TREE_CODE (op0) == VALUE_HANDLE)
+ {
+ bool retval = set_contains_value (set, op0);
+ if (retval)
+ return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
+ block);
+ return false;
+ }
+ }
+ }
return false;
case tcc_exceptional:
@@ -1306,8 +1521,7 @@ valid_in_set (value_set_t set, tree expr
return true;
case tcc_declaration:
- /* VAR_DECL and PARM_DECL are never anticipatable. */
- return false;
+ return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
default:
/* No other cases should be encountered. */
@@ -1320,7 +1534,7 @@ valid_in_set (value_set_t set, tree expr
in SET. */
static void
-clean (value_set_t set)
+clean (value_set_t set, basic_block block)
{
value_set_node_t node;
value_set_node_t next;
@@ -1328,7 +1542,7 @@ clean (value_set_t set)
while (node)
{
next = node->next;
- if (!valid_in_set (set, node->expr))
+ if (!valid_in_set (set, node->expr, block))
set_remove (set, node->expr);
node = next;
}
@@ -1402,6 +1616,7 @@ compute_antic_aux (basic_block block, bo
{
tree val;
value_set_node_t next = node->next;
+
val = get_value_handle (node->expr);
if (!set_contains_value (ANTIC_IN (bprime), val))
set_remove (ANTIC_OUT, node->expr);
@@ -1424,7 +1639,7 @@ compute_antic_aux (basic_block block, bo
for (node = S->head; node; node = node->next)
value_insert_into_set (ANTIC_IN (block), node->expr);
- clean (ANTIC_IN (block));
+ clean (ANTIC_IN (block), block);
if (!set_equal (old, ANTIC_IN (block)))
changed = true;
@@ -1492,7 +1707,304 @@ compute_antic (void)
fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
}
+/* Print the names represented by the bitmap NAMES, to the file OUT. */
+static void
+dump_bitmap_of_names (FILE *out, bitmap names)
+{
+ bitmap_iterator bi;
+ unsigned int i;
+
+ fprintf (out, " { ");
+ EXECUTE_IF_SET_IN_BITMAP (names, 0, i, bi)
+ {
+ print_generic_expr (out, ssa_name (i), 0);
+ fprintf (out, " ");
+ }
+ fprintf (out, "}\n");
+}
+
+ /* Compute a set of representative vuse versions for each phi. This
+ is so we can compute conservative kill sets in terms of all vuses
+ that are killed, instead of continually walking chains.
+
+ We also have to be able kill all names associated with a phi when
+ the phi dies in order to ensure we don't generate overlapping
+ live ranges, which are not allowed in virtual SSA. */
+
+static bitmap *vuse_names;
+static void
+compute_vuse_representatives (void)
+{
+ tree phi;
+ basic_block bb;
+ VEC (tree, heap) *phis = NULL;
+ bool changed = true;
+ size_t i;
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb);
+ phi;
+ phi = PHI_CHAIN (phi))
+ if (!is_gimple_reg (PHI_RESULT (phi)))
+ VEC_safe_push (tree, heap, phis, phi);
+ }
+
+ while (changed)
+ {
+ changed = false;
+
+ for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
+ {
+ size_t ver = SSA_NAME_VERSION (PHI_RESULT (phi));
+ use_operand_p usep;
+ ssa_op_iter iter;
+
+ if (vuse_names[ver] == NULL)
+ {
+ vuse_names[ver] = BITMAP_ALLOC (&grand_bitmap_obstack);
+ bitmap_set_bit (vuse_names[ver], ver);
+ }
+ FOR_EACH_PHI_ARG (usep, phi, iter, SSA_OP_ALL_USES)
+ {
+ tree use = USE_FROM_PTR (usep);
+ bitmap usebitmap = get_representative (vuse_names,
+ SSA_NAME_VERSION (use));
+ if (usebitmap != NULL)
+ {
+ changed |= bitmap_ior_into (vuse_names[ver],
+ usebitmap);
+ }
+ else
+ {
+ changed |= !bitmap_bit_p (vuse_names[ver],
+ SSA_NAME_VERSION (use));
+ if (changed)
+ bitmap_set_bit (vuse_names[ver],
+ SSA_NAME_VERSION (use));
+ }
+ }
+ }
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
+ {
+ bitmap reps = get_representative (vuse_names,
+ SSA_NAME_VERSION (PHI_RESULT (phi)));
+ if (reps)
+ {
+ print_generic_expr (dump_file, PHI_RESULT (phi), 0);
+ fprintf (dump_file, " represents ");
+ dump_bitmap_of_names (dump_file, reps);
+ }
+ }
+ VEC_free (tree, heap, phis);
+}
+
+/* Compute reaching vuses. This is a small bit of iterative dataflow
+ to determine what virtual uses reach what blocks. Because we can't
+ generate overlapping virtual uses, and virtual uses *do* actually
+ die, this ends up being faster in most cases than continually
+ walking the virtual use/def chains to determine whether we are
+ inside a block where a given virtual is still available to be
+ used. */
+
+static void
+compute_rvuse (void)
+{
+
+ size_t i;
+ tree phi;
+ basic_block bb;
+ int *postorder;
+ bool changed = true;
+
+ compute_vuse_representatives ();
+
+ FOR_ALL_BB (bb)
+ {
+ RVUSE_IN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
+ RVUSE_GEN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
+ RVUSE_KILL (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
+ RVUSE_OUT (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
+ }
+
+
+ /* Mark live on entry */
+ for (i = 0; i < num_ssa_names; i++)
+ {
+ tree name = ssa_name (i);
+ if (name && !is_gimple_reg (name)
+ && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (name)))
+ bitmap_set_bit (RVUSE_OUT (ENTRY_BLOCK_PTR),
+ SSA_NAME_VERSION (name));
+ }
+
+ /* Compute local sets for reaching vuses.
+ GEN(block) = generated in block and not locally killed.
+ KILL(block) = set of vuses killed in block.
+ */
+
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator bsi;
+ ssa_op_iter iter;
+ def_operand_p defp;
+ use_operand_p usep;
+
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ FOR_EACH_SSA_USE_OPERAND (usep, stmt, iter, SSA_OP_VIRTUAL_KILLS
+ | SSA_OP_VMAYUSE)
+ {
+ tree use = USE_FROM_PTR (usep);
+ bitmap repbit = get_representative (vuse_names,
+ SSA_NAME_VERSION (use));
+ if (repbit != NULL)
+ {
+ bitmap_and_compl_into (RVUSE_GEN (bb), repbit);
+ bitmap_ior_into (RVUSE_KILL (bb), repbit);
+ }
+ else
+ {
+ bitmap_set_bit (RVUSE_KILL (bb), SSA_NAME_VERSION (use));
+ bitmap_clear_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (use));
+ }
+ }
+ FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+ {
+ tree def = DEF_FROM_PTR (defp);
+ bitmap_set_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (def));
+ }
+ }
+ }
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ if (!is_gimple_reg (PHI_RESULT (phi)))
+ {
+ edge e;
+ edge_iterator ei;
+
+ tree def = PHI_RESULT (phi);
+ /* In reality, the PHI result is generated at the end of
+ each predecessor block. This will make the value
+ LVUSE_IN for the bb containing the PHI, which is
+ correct. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ bitmap_set_bit (RVUSE_GEN (e->src), SSA_NAME_VERSION (def));
+ }
+ }
+ }
+
+ /* Solve reaching vuses.
+
+ RVUSE_IN[BB] = Union of RVUSE_OUT of predecessors.
+ RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB])
+ */
+ postorder = xmalloc (sizeof (int) * (n_basic_blocks - NUM_FIXED_BLOCKS));
+ pre_and_rev_post_order_compute (NULL, postorder, false);
+
+ changed = true;
+ while (changed)
+ {
+ int j;
+ changed = false;
+ for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
+ {
+ edge e;
+ edge_iterator ei;
+ bb = BASIC_BLOCK (postorder[j]);
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ bitmap_ior_into (RVUSE_IN (bb), RVUSE_OUT (e->src));
+
+ changed |= bitmap_ior_and_compl (RVUSE_OUT (bb),
+ RVUSE_GEN (bb),
+ RVUSE_IN (bb),
+ RVUSE_KILL (bb));
+ }
+ }
+ free (postorder);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ FOR_ALL_BB (bb)
+ {
+ fprintf (dump_file, "RVUSE_IN (%d) =", bb->index);
+ dump_bitmap_of_names (dump_file, RVUSE_IN (bb));
+
+ fprintf (dump_file, "RVUSE_KILL (%d) =", bb->index);
+ dump_bitmap_of_names (dump_file, RVUSE_KILL (bb));
+
+ fprintf (dump_file, "RVUSE_GEN (%d) =", bb->index);
+ dump_bitmap_of_names (dump_file, RVUSE_GEN (bb));
+
+ fprintf (dump_file, "RVUSE_OUT (%d) =", bb->index);
+ dump_bitmap_of_names (dump_file, RVUSE_OUT (bb));
+ }
+ }
+}
+
+/* Return true if we can value number the call in STMT. This is true
+ if we have a pure or constant call. */
+
+static bool
+can_value_number_call (tree stmt)
+{
+ tree call = get_call_expr_in (stmt);
+
+ if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
+ return true;
+ return false;
+}
+
+/* Return true if OP is a tree which we can perform value numbering
+ on. */
+
+static bool
+can_value_number_operation (tree op)
+{
+ return UNARY_CLASS_P (op)
+ || BINARY_CLASS_P (op)
+ || COMPARISON_CLASS_P (op)
+ || REFERENCE_CLASS_P (op)
+ || (TREE_CODE (op) == CALL_EXPR
+ && can_value_number_call (op));
+}
+
+
+/* Return true if OP is a tree which we can perform PRE on
+ on. This may not match the operations we can value number, but in
+ a perfect world would. */
+
+static bool
+can_PRE_operation (tree op)
+{
+ return UNARY_CLASS_P (op)
+ || BINARY_CLASS_P (op)
+ || COMPARISON_CLASS_P (op)
+ || TREE_CODE (op) == INDIRECT_REF
+ || TREE_CODE (op) == CALL_EXPR;
+}
+
+
+/* Inserted expressions are placed onto this worklist, which is used
+ for performing quick dead code elimination of insertions we made
+ that didn't turn out to be necessary. */
static VEC(tree,heap) *inserted_exprs;
+
+/* Pool allocated fake store expressions are placed onto this
+ worklist, which, after performing dead code elimination, is walked
+ to see which expressions need to be put into GC'able memory */
+static VEC(tree, heap) *need_creation;
+
+
/* Find a leader for an expression, or generate one using
create_expression_by_pieces if it's ANTIC but
complex.
@@ -1512,11 +2024,8 @@ find_or_generate_expression (basic_block
if (genop == NULL)
{
genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
- gcc_assert (UNARY_CLASS_P (genop)
- || BINARY_CLASS_P (genop)
- || COMPARISON_CLASS_P (genop)
- || REFERENCE_CLASS_P (genop)
- || TREE_CODE (genop) == CALL_EXPR);
+
+ gcc_assert (can_PRE_operation (genop));
genop = create_expression_by_pieces (block, genop, stmts);
}
return genop;
@@ -1568,9 +2077,9 @@ create_expression_by_pieces (basic_block
genwalker && walker;
genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker))
{
- TREE_VALUE (genwalker) = find_or_generate_expression (block,
- TREE_VALUE (walker),
- stmts);
+ TREE_VALUE (genwalker)
+ = find_or_generate_expression (block, TREE_VALUE (walker),
+ stmts);
}
if (op2)
@@ -1582,6 +2091,16 @@ create_expression_by_pieces (basic_block
}
break;
+ case tcc_reference:
+ gcc_assert (TREE_CODE (expr) == INDIRECT_REF);
+ {
+ tree op1 = TREE_OPERAND (expr, 0);
+ tree genop1 = find_or_generate_expression (block, op1, stmts);
+
+ folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
+ genop1);
+ break;
+ }
case tcc_binary:
case tcc_comparison:
@@ -1628,9 +2147,11 @@ create_expression_by_pieces (basic_block
tree val = vn_lookup_or_add (forcedexpr, NULL);
VEC_safe_push (tree, heap, inserted_exprs, stmt);
- vn_add (forcedname, val, NULL);
+ vn_add (forcedname, val);
bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
+ update_stmt (stmt);
+ mark_new_vars_to_rename (tsi_stmt (tsi));
}
tsi = tsi_last (stmts);
tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
@@ -1638,17 +2159,28 @@ create_expression_by_pieces (basic_block
/* Build and insert the assignment of the end result to the temporary
that we will return. */
- temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
+ if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp))
+ {
+ pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp");
+ get_var_ann (pretemp);
+ }
+
+ temp = pretemp;
add_referenced_tmp_var (temp);
+
if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
+
newexpr = build2 (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr);
name = make_ssa_name (temp, newexpr);
TREE_OPERAND (newexpr, 0) = name;
NECESSARY (newexpr) = 0;
+
tsi = tsi_last (stmts);
tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
VEC_safe_push (tree, heap, inserted_exprs, newexpr);
+ update_stmt (newexpr);
+ mark_new_vars_to_rename (newexpr);
/* Add a value handle to the temporary.
The value may already exist in either NEW_SETS, or AVAIL_OUT, because
@@ -1656,7 +2188,7 @@ create_expression_by_pieces (basic_block
the expression may have been represented. There is no harm in replacing
here. */
v = get_value_handle (expr);
- vn_add (name, v, NULL);
+ vn_add (name, v);
bitmap_value_replace_in_set (NEW_SETS (block), name);
bitmap_value_replace_in_set (AVAIL_OUT (block), name);
@@ -1671,14 +2203,14 @@ create_expression_by_pieces (basic_block
return name;
}
-/* Insert the to-be-made-available values of NODE for each predecessor, stored
- in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
- node, given the same value handle as NODE. The prefix of the phi node is
- given with TMPNAME. Return true if we have inserted new stuff. */
+/* Insert the to-be-made-available values of NODE for each
+ predecessor, stored in AVAIL, into the predecessors of BLOCK, and
+ merge the result with a phi node, given the same value handle as
+ NODE. Return true if we have inserted new stuff. */
static bool
insert_into_preds_of_block (basic_block block, value_set_node_t node,
- tree *avail, const char *tmpname)
+ tree *avail)
{
tree val = get_value_handle (node->expr);
edge pred;
@@ -1694,11 +2226,15 @@ insert_into_preds_of_block (basic_block
{
fprintf (dump_file, "Found partial redundancy for expression ");
print_generic_expr (dump_file, node->expr, 0);
+ fprintf (dump_file, " (");
+ print_generic_expr (dump_file, val, 0);
+ fprintf (dump_file, ")");
fprintf (dump_file, "\n");
}
/* Make sure we aren't creating an induction variable. */
- if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
+ if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
+ && TREE_CODE_CLASS (TREE_CODE (node->expr)) != tcc_reference )
{
bool firstinsideloop = false;
bool secondinsideloop = false;
@@ -1723,11 +2259,32 @@ insert_into_preds_of_block (basic_block
tree builtexpr;
bprime = pred->src;
eprime = avail[bprime->index];
- if (BINARY_CLASS_P (eprime)
- || COMPARISON_CLASS_P (eprime)
- || UNARY_CLASS_P (eprime)
- || TREE_CODE (eprime) == CALL_EXPR)
+
+ if (can_PRE_operation (eprime))
{
+#ifdef ENABLE_CHECKING
+ tree vh;
+
+ /* eprime may be an invariant. */
+ vh = TREE_CODE (eprime) == VALUE_HANDLE
+ ? eprime
+ : get_value_handle (eprime);
+
+ /* ensure that the virtual uses we need reach our block. */
+ if (TREE_CODE (vh) == VALUE_HANDLE)
+ {
+ int i;
+ tree vuse;
+ for (i = 0;
+ VEC_iterate (tree, VALUE_HANDLE_VUSES (vh), i, vuse);
+ i++)
+ {
+ size_t id = SSA_NAME_VERSION (vuse);
+ gcc_assert (bitmap_bit_p (RVUSE_OUT (bprime), id)
+ || IS_EMPTY_STMT (SSA_NAME_DEF_STMT (vuse)));
+ }
+ }
+#endif
builtexpr = create_expression_by_pieces (bprime,
eprime,
stmts);
@@ -1746,17 +2303,25 @@ insert_into_preds_of_block (basic_block
return false;
/* Now build a phi for the new variable. */
- temp = create_tmp_var (type, tmpname);
+ if (!prephitemp || TREE_TYPE (prephitemp) != type)
+ {
+ prephitemp = create_tmp_var (type, "prephitmp");
+ get_var_ann (prephitemp);
+ }
+
+ temp = prephitemp;
add_referenced_tmp_var (temp);
+
if (TREE_CODE (type) == COMPLEX_TYPE)
DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
temp = create_phi_node (temp, block);
+
NECESSARY (temp) = 0;
VEC_safe_push (tree, heap, inserted_exprs, temp);
FOR_EACH_EDGE (pred, ei, block->preds)
add_phi_arg (temp, avail[pred->src->index], pred);
- vn_add (PHI_RESULT (temp), val, NULL);
+ vn_add (PHI_RESULT (temp), val);
/* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
this insertion, since we test for the existence of this value in PHI_GEN
@@ -1840,10 +2405,7 @@ insert_aux (basic_block block)
node;
node = node->next)
{
- if (BINARY_CLASS_P (node->expr)
- || COMPARISON_CLASS_P (node->expr)
- || UNARY_CLASS_P (node->expr)
- || TREE_CODE (node->expr) == CALL_EXPR)
+ if (can_PRE_operation (node->expr))
{
tree *avail;
tree val;
@@ -1927,8 +2489,7 @@ insert_aux (basic_block block)
partially redundant. */
if (!cant_insert && !all_same && by_some)
{
- if (insert_into_preds_of_block (block, node, avail,
- "prephitmp"))
+ if (insert_into_preds_of_block (block, node, avail))
new_stuff = true;
}
/* If all edges produce the same value and that value is
@@ -1940,11 +2501,12 @@ insert_aux (basic_block block)
{
value_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
value_set_node_t node;
+
for (node = exprset->head; node; node = node->next)
{
if (TREE_CODE (node->expr) == SSA_NAME)
{
- vn_add (node->expr, eprime, NULL);
+ vn_add (node->expr, eprime);
pre_stats.constified++;
}
}
@@ -2007,7 +2569,7 @@ is_undefined_value (tree expr)
S1 and its value handle to S2.
VUSES represent the virtual use operands associated with EXPR (if
- any). They are used when computing the hash value for EXPR. */
+ any). */
static inline void
add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
@@ -2020,7 +2582,7 @@ add_to_sets (tree var, tree expr, tree s
statements that make aliased stores). In those cases, we are
only interested in making VAR available as its own value. */
if (var != expr)
- vn_add (var, val, NULL_TREE);
+ vn_add (var, val);
if (s1)
bitmap_insert_into_set (s1, var);
@@ -2033,8 +2595,7 @@ add_to_sets (tree var, tree expr, tree s
replaced with the value handles of each of the operands of EXPR.
VUSES represent the virtual use operands associated with EXPR (if
- any). They are used when computing the hash value for EXPR.
- Insert EXPR's operands into the EXP_GEN set for BLOCK. */
+ any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
static inline tree
create_value_expr_from (tree expr, basic_block block, tree stmt)
@@ -2049,7 +2610,8 @@ create_value_expr_from (tree expr, basic
|| TREE_CODE_CLASS (code) == tcc_comparison
|| TREE_CODE_CLASS (code) == tcc_reference
|| TREE_CODE_CLASS (code) == tcc_expression
- || TREE_CODE_CLASS (code) == tcc_exceptional);
+ || TREE_CODE_CLASS (code) == tcc_exceptional
+ || TREE_CODE_CLASS (code) == tcc_declaration);
if (TREE_CODE_CLASS (code) == tcc_unary)
pool = unary_node_pool;
@@ -2167,21 +2729,6 @@ create_value_expr_from (tree expr, basic
}
-/* Return true if we can value number a call. This is true if we have
- a pure or constant call. */
-static bool
-can_value_number_call (tree stmt)
-{
- tree call = get_call_expr_in (stmt);
-
- /* This is a temporary restriction until we translate vuses through
- phi nodes. This is only needed for PRE, of course. */
- if (!in_fre && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
- return false;
- if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
- return true;
- return false;
-}
/* Insert extra phis to merge values that are fully available from
preds of BLOCK, but have no dominating representative coming from
@@ -2221,7 +2768,16 @@ insert_extra_phis (basic_block block, ba
{
tree name = ssa_name (i);
tree val = get_value_handle (name);
- tree temp = create_tmp_var (TREE_TYPE (name), "mergephitmp");
+ tree temp;
+
+ if (!mergephitemp
+ || TREE_TYPE (name) != TREE_TYPE (mergephitemp))
+ {
+ mergephitemp = create_tmp_var (TREE_TYPE (name),
+ "mergephitmp");
+ get_var_ann (mergephitemp);
+ }
+ temp = mergephitemp;
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -2249,7 +2805,7 @@ insert_extra_phis (basic_block block, ba
}
}
- vn_add (PHI_RESULT (temp), val, NULL);
+ vn_add (PHI_RESULT (temp), val);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n");
@@ -2329,6 +2885,174 @@ try_look_through_load (tree lhs, tree me
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. */
+
+static tree
+poolify_tree (tree node)
+{
+ switch (TREE_CODE (node))
+ {
+ case INDIRECT_REF:
+ {
+ tree temp = pool_alloc (reference_node_pool);
+ memcpy (temp, node, tree_size (node));
+ TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
+ return temp;
+ }
+ break;
+ case MODIFY_EXPR:
+ {
+ tree temp = pool_alloc (modify_expr_node_pool);
+ memcpy (temp, node, tree_size (node));
+ TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
+ TREE_OPERAND (temp, 1) = poolify_tree (TREE_OPERAND (temp, 1));
+ return temp;
+ }
+ break;
+ case SSA_NAME:
+ case INTEGER_CST:
+ case STRING_CST:
+ case REAL_CST:
+ case PARM_DECL:
+ case VAR_DECL:
+ case RESULT_DECL:
+ return node;
+ default:
+ gcc_unreachable ();
+ }
+}
+
+static tree modify_expr_template;
+
+/* Allocate a MODIFY_EXPR with TYPE, and operands OP1, OP2 in the
+ alloc pools and return it. */
+static tree
+poolify_modify_expr (tree type, tree op1, tree op2)
+{
+ if (modify_expr_template == NULL)
+ modify_expr_template = build2 (MODIFY_EXPR, type, op1, op2);
+
+ TREE_OPERAND (modify_expr_template, 0) = op1;
+ TREE_OPERAND (modify_expr_template, 1) = op2;
+ TREE_TYPE (modify_expr_template) = type;
+
+ return poolify_tree (modify_expr_template);
+}
+
+
+/* For each real store operation of the form
+ *a = <value> that we see, create a corresponding fake store of the
+ form storetmp_<version> = *a.
+
+ This enables AVAIL computation to mark the results of stores as
+ available. Without this, you'd need to do some computation to
+ mark the result of stores as ANTIC and AVAIL at all the right
+ points.
+ To save memory, we keep the store
+ statements pool allocated until we decide whether they are
+ necessary or not. */
+
+static void
+insert_fake_stores (void)
+{
+ basic_block block;
+
+ FOR_ALL_BB (block)
+ {
+ block_stmt_iterator bsi;
+ for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ /* We can't generate SSA names for stores that are complex
+ or aggregate. We also want to ignore things whose
+ virtual uses occur in abnormal phis. */
+
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == INDIRECT_REF
+ && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 0)))
+ && TREE_CODE (TREE_TYPE (TREE_OPERAND (stmt, 0))) != COMPLEX_TYPE)
+ {
+ ssa_op_iter iter;
+ def_operand_p defp;
+ tree lhs = TREE_OPERAND (stmt, 0);
+ tree rhs = TREE_OPERAND (stmt, 1);
+ tree new;
+ bool notokay = false;
+
+ FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+ {
+ tree defvar = DEF_FROM_PTR (defp);
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
+ {
+ notokay = true;
+ break;
+ }
+ }
+
+ if (notokay)
+ continue;
+
+ if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
+ {
+ storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
+ get_var_ann (storetemp);
+ }
+
+ new = poolify_modify_expr (TREE_TYPE (stmt), storetemp, lhs);
+
+ lhs = make_ssa_name (storetemp, new);
+ TREE_OPERAND (new, 0) = lhs;
+ create_ssa_artficial_load_stmt (new, stmt);
+
+ NECESSARY (new) = 0;
+ VEC_safe_push (tree, heap, inserted_exprs, new);
+ VEC_safe_push (tree, heap, need_creation, new);
+ bsi_insert_after (&bsi, new, BSI_NEW_STMT);
+ }
+ }
+ }
+}
+
+/* Turn the pool allocated fake stores that we created back into real
+ GC allocated ones if they turned out to be necessary to PRE some
+ expressions. */
+
+static void
+realify_fake_stores (void)
+{
+ unsigned int i;
+ tree stmt;
+
+ for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
+ {
+ if (NECESSARY (stmt))
+ {
+ block_stmt_iterator bsi;
+ tree newstmt;
+
+ /* Mark the temp variable as referenced */
+ add_referenced_tmp_var (SSA_NAME_VAR (TREE_OPERAND (stmt, 0)));
+
+ /* Put the new statement in GC memory, fix up the annotation
+ and SSA_NAME_DEF_STMT on it, and then put it in place of
+ the old statement in the IR stream. */
+ newstmt = unshare_expr (stmt);
+ SSA_NAME_DEF_STMT (TREE_OPERAND (newstmt, 0)) = newstmt;
+
+ newstmt->common.ann = stmt->common.ann;
+
+ bsi = bsi_for_stmt (stmt);
+ bsi_replace (&bsi, newstmt, true);
+ }
+ else
+ release_defs (stmt);
+ }
+}
+
+
/* Compute the AVAIL set for all basic blocks.
This function performs value numbering of the statements in each basic
@@ -2410,10 +3134,10 @@ compute_avail (void)
stmt = bsi_stmt (bsi);
ann = stmt_ann (stmt);
- /* We are only interested in assignments of the form
- X_i = EXPR, where EXPR represents an "interesting"
- computation, it has no volatile operands and X_i
- doesn't flow through an abnormal edge. */
+ /* For regular value numbering, we are only interested in
+ assignments of the form X_i = EXPR, where EXPR represents
+ an "interesting" computation, it has no volatile operands
+ and X_i doesn't flow through an abnormal edge. */
if (TREE_CODE (stmt) == MODIFY_EXPR
&& !ann->has_volatile_ops
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
@@ -2429,17 +3153,11 @@ compute_avail (void)
continue;
STRIP_USELESS_TYPE_CONVERSION (rhs);
- if (UNARY_CLASS_P (rhs)
- || BINARY_CLASS_P (rhs)
- || COMPARISON_CLASS_P (rhs)
- || REFERENCE_CLASS_P (rhs)
- || (TREE_CODE (rhs) == CALL_EXPR
- && can_value_number_call (stmt)))
+ if (can_value_number_operation (rhs))
{
- /* For binary, unary, and reference expressions,
- create a duplicate expression with the operands
- replaced with the value handles of the original
- 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)
{
@@ -2582,6 +3300,9 @@ mark_operand_necessary (tree op)
gcc_assert (op);
+ if (TREE_CODE (op) != SSA_NAME)
+ return NULL;
+
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (stmt);
@@ -2614,14 +3335,12 @@ remove_dead_inserted_code (void)
while (VEC_length (tree, worklist) > 0)
{
t = VEC_pop (tree, worklist);
+
+ /* PHI nodes are somewhat special in that each PHI alternative has
+ data and control dependencies. All the statements feeding the
+ PHI node's arguments are always necessary. */
if (TREE_CODE (t) == PHI_NODE)
{
- /* PHI nodes are somewhat special in that each PHI alternative has
- data and control dependencies. All the statements feeding the
- PHI node's arguments are always necessary. In aggressive mode,
- we also consider the control dependent edges leading to the
- predecessor block associated with each PHI alternative as
- necessary. */
int k;
VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
@@ -2657,16 +3376,19 @@ remove_dead_inserted_code (void)
}
}
}
+
for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
{
if (!NECESSARY (t))
{
block_stmt_iterator bsi;
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Removing unnecessary insertion:");
print_generic_stmt (dump_file, t, 0);
}
+
if (TREE_CODE (t) == PHI_NODE)
{
remove_phi_node (t, NULL);
@@ -2675,11 +3397,13 @@ remove_dead_inserted_code (void)
{
bsi = bsi_for_stmt (t);
bsi_remove (&bsi);
+ release_defs (t);
}
}
}
VEC_free (tree, heap, worklist);
}
+
/* Initialize data structures used by PRE. */
static void
@@ -2690,9 +3414,16 @@ init_pre (bool do_fre)
in_fre = do_fre;
inserted_exprs = NULL;
+ need_creation = NULL;
+ pretemp = NULL_TREE;
+ storetemp = NULL_TREE;
+ mergephitemp = NULL_TREE;
+ prephitemp = NULL_TREE;
+
vn_init ();
if (!do_fre)
current_loops = loop_optimizer_init (dump_file);
+
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
@@ -2733,6 +3464,11 @@ init_pre (bool do_fre)
tree_code_size (TREE_LIST), 30);
comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
tree_code_size (EQ_EXPR), 30);
+ modify_expr_node_pool = create_alloc_pool ("MODIFY_EXPR nodes",
+ tree_code_size (MODIFY_EXPR),
+ 30);
+ modify_expr_template = NULL;
+
FOR_ALL_BB (bb)
{
EXP_GEN (bb) = set_new (true);
@@ -2754,6 +3490,7 @@ fini_pre (bool do_fre)
unsigned int i;
VEC_free (tree, heap, inserted_exprs);
+ VEC_free (tree, heap, need_creation);
bitmap_obstack_release (&grand_bitmap_obstack);
free_alloc_pool (value_set_pool);
free_alloc_pool (bitmap_set_pool);
@@ -2764,6 +3501,7 @@ fini_pre (bool do_fre)
free_alloc_pool (list_node_pool);
free_alloc_pool (expression_node_pool);
free_alloc_pool (comparison_node_pool);
+ free_alloc_pool (modify_expr_node_pool);
htab_delete (phi_translate_table);
remove_fake_exit_edges ();
@@ -2804,7 +3542,6 @@ fini_pre (bool do_fre)
}
}
-
/* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
only wants to do full redundancy elimination. */
@@ -2813,6 +3550,9 @@ execute_pre (bool do_fre)
{
init_pre (do_fre);
+ if (!do_fre)
+ insert_fake_stores ();
+
/* Collect and value number expressions computed in each basic block. */
compute_avail ();
@@ -2837,8 +3577,11 @@ execute_pre (bool do_fre)
computing ANTIC, either, even though it's plenty fast. */
if (!do_fre && n_basic_blocks < 4000)
{
+ vuse_names = xcalloc (num_ssa_names, sizeof (bitmap));
+ compute_rvuse ();
compute_antic ();
insert ();
+ free (vuse_names);
}
/* Remove all the redundant expressions. */
@@ -2854,13 +3597,17 @@ execute_pre (bool do_fre)
}
bsi_commit_edge_inserts ();
+
if (!do_fre)
- remove_dead_inserted_code ();
+ {
+ remove_dead_inserted_code ();
+ realify_fake_stores ();
+ }
+
fini_pre (do_fre);
}
-
/* Gate and execute functions for PRE. */
static void
Index: tree-flow.h
===================================================================
--- tree-flow.h (revision 109165)
+++ tree-flow.h (working copy)
@@ -776,10 +776,14 @@ void print_value_expressions (FILE *, tr
/* In tree-vn.c */
bool expressions_equal_p (tree, tree);
tree get_value_handle (tree);
-hashval_t vn_compute (tree, hashval_t, tree);
+hashval_t vn_compute (tree, hashval_t);
+void sort_vuses (VEC (tree, gc) *);
tree vn_lookup_or_add (tree, tree);
-void vn_add (tree, tree, tree);
+tree vn_lookup_or_add_with_vuses (tree, VEC (tree, gc) *);
+void vn_add (tree, tree);
+void vn_add_with_vuses (tree, tree, VEC (tree, gc) *);
tree vn_lookup (tree, tree);
+tree vn_lookup_with_vuses (tree, VEC (tree, gc) *);
void vn_init (void);
void vn_delete (void);
Index: passes.c
===================================================================
--- passes.c (revision 109165)
+++ passes.c (working copy)
@@ -554,6 +554,7 @@ init_optimization_passes (void)
NEXT_PASS (pass_cse_reciprocals);
NEXT_PASS (pass_split_crit_edges);
NEXT_PASS (pass_pre);
+ NEXT_PASS (pass_may_alias);
NEXT_PASS (pass_sink_code);
NEXT_PASS (pass_tree_loop);
NEXT_PASS (pass_reassoc);
Index: testsuite/gcc.dg/tree-ssa/loadpre6.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/loadpre6.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/loadpre6.c (revision 0)
@@ -0,0 +1,74 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+
+union tree_node;
+typedef union tree_node *tree;
+
+struct tree_common
+{
+ tree chain;
+};
+
+struct tree_list
+{
+ struct tree_common common;
+ tree value;
+};
+
+union tree_node
+
+{
+ struct tree_common common;
+ struct tree_list list;
+};
+
+extern void abort (void) __attribute__((noreturn));
+
+void __attribute__((noinline))
+foo (void)
+{
+ abort ();
+}
+
+void __attribute__((noinline))
+remove_useless_vars (tree *unexpanded_var_list, int dump_file)
+{
+ tree var, *cell;
+ int c = 0;
+ for (cell = unexpanded_var_list; *cell; )
+ {
+ var = (*cell)->list.value;
+ if (var)
+ {
+ if (dump_file)
+ foo ();
+
+ *cell = ((*cell)->common.chain);
+ continue;
+ }
+
+ cell = &((*cell)->common.chain);
+ }
+}
+extern void *malloc (int) __attribute__ ((malloc));
+
+int
+main (void)
+{
+ int i;
+ tree unexpanded_var_list, last = (tree) 0;
+
+ for (i = 0; i < 2; i++)
+ {
+ unexpanded_var_list = malloc (sizeof (struct tree_list));
+ unexpanded_var_list->list.value = (tree) (long unsigned) (i & 1);
+ unexpanded_var_list->common.chain = last;
+ last = unexpanded_var_list;
+ }
+
+ remove_useless_vars (&unexpanded_var_list, 0);
+ return 0;
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre" } } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
+
Index: testsuite/gcc.dg/tree-ssa/loadpre7.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/loadpre7.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/loadpre7.c (revision 0)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+/* We can't eliminate the *p load here in any sane way, as eshup8 may
+ change it. */
+void
+enormlz (x)
+ unsigned short x[];
+{
+ register unsigned short *p;
+ p = &x[2];
+ while ((*p & 0xff00) == 0)
+ {
+ eshup8 (x);
+ }
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 0" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Index: testsuite/gcc.dg/tree-ssa/loadpre8.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/loadpre8.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/loadpre8.c (revision 0)
@@ -0,0 +1,97 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+typedef union tree_node *tree;
+struct tree_common
+{
+ tree chain;
+}
+VEC_constructor_elt_base;
+struct tree_ssa_name
+{
+ tree var;
+};
+union tree_node
+{
+ struct tree_common common;
+ struct tree_ssa_name ssa_name;
+};
+struct edge_def
+{
+ struct basic_block_def *dest;
+};
+typedef struct edge_def *edge;
+typedef struct VEC_edge_base
+{
+}
+VEC_edge_base;
+edge
+VEC_edge_base_index (const VEC_edge_base * vec_, unsigned ix_)
+{
+}
+typedef struct VEC_edge_gc
+{
+ VEC_edge_base base;
+}
+VEC_edge_gc;
+struct basic_block_def
+{
+ VEC_edge_gc *succs;
+};
+typedef struct basic_block_def *basic_block;
+typedef struct
+{
+ unsigned index;
+ VEC_edge_gc **container;
+}
+edge_iterator;
+__inline__ VEC_edge_gc *
+ei_container (edge_iterator i)
+{
+ return *i.container;
+}
+__inline__ edge_iterator
+ei_start_1 (VEC_edge_gc ** ev)
+{
+ edge_iterator i;
+ i.container = ev;
+ return i;
+}
+ei_next (edge_iterator * i)
+{
+}
+static __inline__ edge
+ei_edge (edge_iterator i)
+{
+ return (edge) (VEC_edge_base_index ((((ei_container (i))) ? &((ei_container (i)))->base : 0), (i.index)));
+}
+static __inline__ unsigned char
+ei_cond (edge_iterator ei, edge * p)
+{
+ *p = ei_edge (ei);
+}
+typedef tree *def_operand_p;
+extern tree *get_phi_result_ptr (tree);
+static __inline__ tree
+get_def_from_ptr (def_operand_p def)
+{
+}
+tree
+phi_nodes (basic_block bb)
+{
+}
+
+/* We can eliminate a load of the SRA'd variable edge_iterator.container */
+rewrite_add_phi_arguments (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+ for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei), &(e));
+ ei_next (&(ei)))
+ {
+ tree phi;
+ for (phi = phi_nodes (e->dest); phi; phi = (((phi))->common.chain))
+ get_reaching_def ((get_def_from_ptr (get_phi_result_ptr (phi)))->ssa_name.var);
+ }
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Index: testsuite/gcc.dg/tree-ssa/loadpre1.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/loadpre1.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/loadpre1.c (revision 0)
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int main(int *a, int argc)
+{
+ int c;
+ int d, e;
+
+ /* Should be able to eliminate the second load of *a along the main path. */
+ d = *a;
+ if (argc)
+ {
+ a = &c;
+ }
+ e = *a;
+ return d + e;
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Index: testsuite/gcc.dg/tree-ssa/loadpre2.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/loadpre2.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/loadpre2.c (revision 0)
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int main(int *a, int argc)
+{
+ int b;
+ int i;
+ int d, e;
+
+ /* Should be able to hoist this out of the loop. */
+ for (i = 0; i < argc; i++)
+ {
+ e = *a;
+ }
+ return d + e;
+}
+
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Index: testsuite/gcc.dg/tree-ssa/loadpre3.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/loadpre3.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/loadpre3.c (revision 0)
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int main(int **a,int argc)
+{
+ int b;
+ int d, e;
+
+ if (argc)
+ {
+ d = *(*a);
+ }
+ else
+ {
+
+ }
+ /* Should be able to eliminate one of the *(*a)'s along the if path
+ by pushing it into the else path. We will also eliminate
+ one of the *a's. */
+ e = *(*a);
+ return d + e;
+}
+
+/* { dg-final { scan-tree-dump-times "Eliminated: 2" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Index: testsuite/gcc.dg/tree-ssa/loadpre4.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/loadpre4.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/loadpre4.c (revision 0)
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int main(int *a, int argc)
+{
+ int b;
+ int c;
+ int i;
+ int d, e;
+
+ /* With smarter load PRE, we'd be able to recompute the value at the
+ kill point. arguably not worth it. */
+ for (i = 0; i < argc; i++)
+ {
+ e = *a;
+ *a = 9;
+ }
+ return d + e;
+}
+
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
Index: testsuite/gcc.dg/tree-ssa/loadpre5.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/loadpre5.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/loadpre5.c (revision 0)
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int p;
+int r;
+int a(void)
+{
+ return p;
+}
+int main(int argc)
+{
+ int q;
+ q = a();
+
+ /* We should be able to move the call to a into the if path.
+ in a perfect world, we'd actually decide that it can't touch
+ r, and not recompute it at all!. */
+ if (argc)
+ r = 9;
+ return q + a();
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */