/* SSA-PRE for trees.
- Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
+ Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
<stevenb@suse.de>
#include "tree-iterator.h"
#include "real.h"
#include "alloc-pool.h"
+#include "obstack.h"
#include "tree-pass.h"
#include "flags.h"
#include "bitmap.h"
#include "langhooks.h"
#include "cfgloop.h"
+#include "tree-ssa-sccvn.h"
/* TODO:
we can repair later on.
3. We can do back-substitution or smarter value numbering to catch
commutative expressions split up over multiple statements.
- 4. ANTIC_SAFE_LOADS could be a lot smarter than it is now.
- Right now, it is simply calculating loads that occur before
- any store in a block, instead of loads that occur before
- stores that affect them. This is relatively more expensive, and
- it's not clear how much more it will buy us.
*/
/* For ease of terminology, "expression node" in the below refers to
- every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
- the actual statement containing the expressions we care about, and
- we cache the value number by putting it in the expression. */
+ every expression node but GIMPLE_MODIFY_STMT, because GIMPLE_MODIFY_STMT's
+ represent the actual statement containing the expressions we care about,
+ and we cache the value number by putting it in the expression. */
/* Basic algorithm
Next, we generate the ANTIC sets. These sets represent the
anticipatable expressions. ANTIC is a backwards dataflow
- problem.An expression is anticipatable in a given block if it could
+ problem. An expression is anticipatable in a given block if it could
be generated in that block. This means that if we had to perform
an insertion in that block, of the value of that expression, we
could. Calculating the ANTIC sets requires phi translation of
In order to make it fully redundant, we insert the expression into
the predecessors where it is not available, but is ANTIC.
- insert/insert_aux performs this insertion.
+
+ For the partial anticipation case, we only perform insertion if it
+ is partially anticipated in some block, and fully available in all
+ of the predecessors.
+
+ insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
+ performs these steps.
Fourth, we eliminate fully redundant expressions.
This is a simple statement walk that replaces redundant
Value numbers are represented using the "value handle" approach.
This means that each SSA_NAME (and for other reasons to be
disclosed in a moment, expression nodes) has a value handle that
- can be retrieved through get_value_handle. This value handle, *is*
+ can be retrieved through get_value_handle. This value handle *is*
the value number of the SSA_NAME. You can pointer compare the
value handles for equivalence purposes.
For debugging reasons, the value handle is internally more than
- just a number, it is a VAR_DECL named "value.x", where x is a
+ just a number, it is a VALUE_HANDLE named "VH.x", where x is a
unique number for each value number in use. This allows
expressions with SSA_NAMES replaced by value handles to still be
- pretty printed in a sane way. They simply print as "value.3 *
- value.5", etc.
+ pretty printed in a sane way. They simply print as "VH.3 *
+ VH.5", etc.
Expression nodes have value handles associated with them as a
cache. Otherwise, we'd have to look them up again in the hash
this pass.
All of this also means that if you print the EXP_GEN or ANTIC sets,
- you will see "value.5 + value.7" in the set, instead of "a_55 +
+ you will see "VH.5 + VH.7" in the set, instead of "a_55 +
b_66" or something. The only thing that actually cares about
seeing the value leaders is phi translation, and it needs to be
able to find the leader for a value in an arbitrary block, so this
useful only for debugging, since we don't do identity lookups. */
-static bool in_fre = false;
+/* Next global expression id number. */
+static unsigned int next_expression_id;
+
+/* Mapping from expression to id number we can use in bitmap sets. */
+static VEC(tree, heap) *expressions;
-/* A value set element. Basically a single linked list of
- expressions/values. */
-typedef struct value_set_node
+/* Allocate an expression id for EXPR. */
+
+static inline unsigned int
+alloc_expression_id (tree expr)
{
- /* An expression. */
- tree expr;
+ tree_ann_common_t ann;
+
+ ann = get_tree_common_ann (expr);
+
+ /* Make sure we won't overflow. */
+ gcc_assert (next_expression_id + 1 > next_expression_id);
- /* A pointer to the next element of the value set. */
- struct value_set_node *next;
-} *value_set_node_t;
+ ann->aux = XNEW (unsigned int);
+ * ((unsigned int *)ann->aux) = next_expression_id++;
+ VEC_safe_push (tree, heap, expressions, expr);
+ return next_expression_id - 1;
+}
+/* Return the expression id for tree EXPR. */
-/* A value set. This is a singly linked list of value_set_node
- elements with a possible bitmap that tells us what values exist in
- the set. This set must be kept in topologically sorted order. */
-typedef struct value_set
+static inline unsigned int
+get_expression_id (tree expr)
{
- /* The head of the list. Used for iterating over the list in
- order. */
- value_set_node_t head;
+ tree_ann_common_t ann = tree_common_ann (expr);
+ gcc_assert (ann);
+ gcc_assert (ann->aux);
- /* The tail of the list. Used for tail insertions, which are
- necessary to keep the set in topologically sorted order because
- of how the set is built. */
- value_set_node_t tail;
+ return *((unsigned int *)ann->aux);
+}
- /* The length of the list. */
- size_t length;
+/* Return the existing expression id for EXPR, or create one if one
+ does not exist yet. */
- /* True if the set is indexed, which means it contains a backing
- bitmap for quick determination of whether certain values exist in the
- set. */
- bool indexed;
+static inline unsigned int
+get_or_alloc_expression_id (tree expr)
+{
+ tree_ann_common_t ann = tree_common_ann (expr);
- /* The bitmap of values that exist in the set. May be NULL in an
- empty or non-indexed set. */
- bitmap values;
+ if (ann == NULL || !ann->aux)
+ return alloc_expression_id (expr);
+
+ return get_expression_id (expr);
+}
+
+/* Return the expression that has expression id ID */
+
+static inline tree
+expression_for_id (unsigned int id)
+{
+ return VEC_index (tree, expressions, id);
+}
+
+/* Free the expression id field in all of our expressions,
+ and then destroy the expressions array. */
+
+static void
+clear_expression_ids (void)
+{
+ int i;
+ tree expr;
-} *value_set_t;
+ for (i = 0; VEC_iterate (tree, expressions, i, expr); i++)
+ {
+ free (tree_common_ann (expr)->aux);
+ tree_common_ann (expr)->aux = NULL;
+ }
+ VEC_free (tree, heap, expressions);
+}
+static bool in_fre = false;
/* An unordered bitmap set. One bitmap tracks values, the other,
expressions. */
bitmap values;
} *bitmap_set_t;
+#define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
+ EXECUTE_IF_SET_IN_BITMAP(set->expressions, 0, id, bi)
+
/* Sets that we need to keep track of. */
-typedef struct bb_value_sets
+typedef struct bb_bitmap_sets
{
/* The EXP_GEN set, which represents expressions/values generated in
a basic block. */
- value_set_t exp_gen;
+ bitmap_set_t exp_gen;
/* The PHI_GEN set, which represents PHI results generated in a
basic block. */
/* The ANTIC_IN set, which represents which values are anticipatable
in a given basic block. */
- value_set_t antic_in;
+ bitmap_set_t antic_in;
+
+ /* The PA_IN set, which represents which values are
+ partially anticipatable in a given basic block. */
+ bitmap_set_t pa_in;
/* The NEW_SETS set, which is used during insertion to augment the
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;
-
- /* For actually occurring loads, as long as they occur before all the
- other stores in the block, we know they are antic at the top of
- the block, regardless of RVUSE_KILL. */
- value_set_t antic_safe_loads;
+ /* True if we have visited this block during ANTIC calculation. */
+ unsigned int visited:1;
+
+ /* True we have deferred processing this block during ANTIC
+ calculation until its successor is processed. */
+ unsigned int deferred : 1;
} *bb_value_sets_t;
#define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
#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 PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
-#define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads
+#define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
+#define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
+
+/* Maximal set of values, used to initialize the ANTIC problem, which
+ is an intersection problem. */
+static bitmap_set_t maximal_set;
+
+/* Basic block list in postorder. */
+static int *postorder;
/* This structure is used to keep track of statistics on what
optimization PRE was able to perform. */
/* The number of new expressions/temporaries generated by PRE. */
int insertions;
+ /* The number of inserts found due to partial anticipation */
+ int pa_insert;
+
/* The number of new PHI nodes added by PRE. */
int phis;
} pre_stats;
-
+static bool do_partial_partial;
static tree bitmap_find_leader (bitmap_set_t, tree);
-static tree find_leader (value_set_t, tree);
-static void value_insert_into_set (value_set_t, tree);
static void bitmap_value_insert_into_set (bitmap_set_t, tree);
static void bitmap_value_replace_in_set (bitmap_set_t, tree);
-static void insert_into_set (value_set_t, tree);
static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
static bool bitmap_set_contains_value (bitmap_set_t, tree);
+static void bitmap_insert_into_set (bitmap_set_t, tree);
static bitmap_set_t bitmap_set_new (void);
-static value_set_t set_new (bool);
static bool is_undefined_value (tree);
static tree create_expression_by_pieces (basic_block, tree, tree);
static tree find_or_generate_expression (basic_block, tree, tree);
-
/* We can add and remove elements and entries to and from sets
and hash tables, so we use alloc pools for them. */
-static alloc_pool value_set_pool;
static alloc_pool bitmap_set_pool;
-static alloc_pool value_set_node_pool;
static alloc_pool binary_node_pool;
static alloc_pool unary_node_pool;
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;
+/* We can't use allocation pools to hold temporary CALL_EXPR objects, since
+ they are not of fixed size. Instead, use an obstack. */
+
+static struct obstack temp_call_expr_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;
+/* Which expressions have been seen during a given phi translation. */
+static bitmap seen_during_translate;
+
/* The phi_translate_table caches phi translations for a given
expression and predecessor. */
/* 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;
ept.e = e;
ept.pred = pred;
ept.vuses = vuses;
- ept.hashcode = vn_compute (e, (unsigned long) pred);
+ ept.hashcode = iterative_hash_expr (e, (unsigned long) pred);
slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
NO_INSERT);
if (!slot)
new_pair->pred = pred;
new_pair->vuses = vuses;
new_pair->v = v;
- new_pair->hashcode = vn_compute (e, (unsigned long) pred);
+ new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred);
slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
new_pair->hashcode, INSERT);
if (*slot)
}
-/* Add expression E to the expression set of value V. */
-
-void
-add_to_value (tree v, tree e)
-{
- /* Constants have no expression sets. */
- if (is_gimple_min_invariant (v))
- return;
-
- if (VALUE_HANDLE_EXPR_SET (v) == NULL)
- VALUE_HANDLE_EXPR_SET (v) = set_new (false);
-
- insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
-}
-
-
-/* Return true if value V exists in the bitmap for SET. */
+/* Return true if V is a value expression that represents itself.
+ In our world, this is *only* non-value handles. */
static inline bool
-value_exists_in_set_bitmap (value_set_t set, tree v)
+constant_expr_p (tree v)
{
- if (!set->values)
- return false;
-
- return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
+ return TREE_CODE (v) != VALUE_HANDLE &&
+ (TREE_CODE (v) == FIELD_DECL || is_gimple_min_invariant (v));
}
+/* Add expression E to the expression set of value V. */
-/* Remove value V from the bitmap for SET. */
-
-static void
-value_remove_from_set_bitmap (value_set_t set, tree v)
+void
+add_to_value (tree v, tree e)
{
- gcc_assert (set->indexed);
-
- if (!set->values)
+ /* Constants have no expression sets. */
+ if (constant_expr_p (v))
return;
- bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
-}
-
-
-/* Insert the value number V into the bitmap of values existing in
- SET. */
-
-static inline void
-value_insert_into_set_bitmap (value_set_t set, tree v)
-{
- gcc_assert (set->indexed);
-
- if (set->values == NULL)
- set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
+ if (VALUE_HANDLE_EXPR_SET (v) == NULL)
+ VALUE_HANDLE_EXPR_SET (v) = bitmap_set_new ();
- bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
+ bitmap_insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
}
-
/* Create a new bitmap set and return it. */
static bitmap_set_t
return ret;
}
-/* Create a new set. */
-
-static value_set_t
-set_new (bool indexed)
-{
- value_set_t ret;
- ret = (value_set_t) pool_alloc (value_set_pool);
- ret->head = ret->tail = NULL;
- ret->length = 0;
- ret->indexed = indexed;
- ret->values = NULL;
- return ret;
-}
-
-/* Insert an expression EXPR into a bitmapped set. */
+/* Remove an expression EXPR from a bitmapped set. */
static void
-bitmap_insert_into_set (bitmap_set_t set, tree expr)
+bitmap_remove_from_set (bitmap_set_t set, tree expr)
{
- tree val;
- /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
- gcc_assert (TREE_CODE (expr) == SSA_NAME);
- val = get_value_handle (expr);
+ tree val = get_value_handle (expr);
gcc_assert (val);
- if (!is_gimple_min_invariant (val))
- {
- bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
- bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
- }
+ if (!constant_expr_p (val))
+ {
+ bitmap_clear_bit (set->values, VALUE_HANDLE_ID (val));
+ bitmap_clear_bit (set->expressions, get_expression_id (expr));
+ }
}
-/* Insert EXPR into SET. */
+/* Insert an expression EXPR into a bitmapped set. */
static void
-insert_into_set (value_set_t set, tree expr)
+bitmap_insert_into_set (bitmap_set_t set, tree expr)
{
- value_set_node_t newnode = (value_set_node_t) pool_alloc (value_set_node_pool);
tree val = get_value_handle (expr);
- gcc_assert (val);
- if (is_gimple_min_invariant (val))
- return;
-
- /* For indexed sets, insert the value into the set value bitmap.
- For all sets, add it to the linked list and increment the list
- length. */
- if (set->indexed)
- value_insert_into_set_bitmap (set, val);
-
- newnode->next = NULL;
- newnode->expr = expr;
- set->length ++;
- if (set->head == NULL)
- {
- set->head = set->tail = newnode;
- }
- else
+ gcc_assert (val);
+ if (!constant_expr_p (val))
{
- set->tail->next = newnode;
- set->tail = newnode;
+ bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
+ bitmap_set_bit (set->expressions, get_or_alloc_expression_id (expr));
}
}
bitmap_copy (dest->values, orig->values);
}
-/* Perform bitmapped set operation DEST &= ORIG. */
+/* Free memory used up by SET. */
static void
-bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
+bitmap_set_free (bitmap_set_t set)
{
- bitmap_iterator bi;
- unsigned int i;
- 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)
- {
- tree name = ssa_name (i);
- tree val = get_value_handle (name);
- if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
- bitmap_clear_bit (dest->expressions, i);
- }
- BITMAP_FREE (temp);
+ BITMAP_FREE (set->expressions);
+ BITMAP_FREE (set->values);
}
-/* Perform bitmapped value set operation DEST = DEST & ~ORIG. */
-static void
-bitmap_set_and_compl (bitmap_set_t dest, bitmap_set_t orig)
+/* A comparison function for use in qsort to top sort a bitmap set. Simply
+ subtracts value handle ids, since they are created in topo-order. */
+
+static int
+vh_compare (const void *pa, const void *pb)
{
- bitmap_iterator bi;
- unsigned int i;
- bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
+ const tree vha = get_value_handle (*((const tree *)pa));
+ const tree vhb = get_value_handle (*((const tree *)pb));
- bitmap_and_compl_into (dest->values, orig->values);
- bitmap_copy (temp, dest->expressions);
- EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
+ /* This can happen when we constify things. */
+ if (constant_expr_p (vha))
{
- tree name = ssa_name (i);
- tree val = get_value_handle (name);
- if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
- bitmap_clear_bit (dest->expressions, i);
+ if (constant_expr_p (vhb))
+ return -1;
+ return -1;
}
- BITMAP_FREE (temp);
+ else if (constant_expr_p (vhb))
+ return 1;
+ return VALUE_HANDLE_ID (vha) - VALUE_HANDLE_ID (vhb);
}
-/* Return true if the bitmap set SET is empty. */
+/* Generate an topological-ordered array of bitmap set SET. */
-static bool
-bitmap_set_empty_p (bitmap_set_t set)
+static VEC(tree, heap) *
+sorted_array_from_bitmap_set (bitmap_set_t set)
{
- return bitmap_empty_p (set->values);
-}
-
-/* Copy the set ORIG to the set DEST. */
+ unsigned int i;
+ bitmap_iterator bi;
+ VEC(tree, heap) *result = NULL;
-static void
-set_copy (value_set_t dest, value_set_t orig)
-{
- value_set_node_t node;
+ FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
+ VEC_safe_push (tree, heap, result, expression_for_id (i));
- if (!orig || !orig->head)
- return;
+ qsort (VEC_address (tree, result), VEC_length (tree, result),
+ sizeof (tree), vh_compare);
- for (node = orig->head;
- node;
- node = node->next)
- {
- insert_into_set (dest, node->expr);
- }
+ return result;
}
-/* Remove EXPR from SET. */
+/* Perform bitmapped set operation DEST &= ORIG. */
static void
-set_remove (value_set_t set, tree expr)
+bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
{
- value_set_node_t node, prev;
+ bitmap_iterator bi;
+ unsigned int i;
- /* Remove the value of EXPR from the bitmap, decrement the set
- length, and remove it from the actual double linked list. */
- value_remove_from_set_bitmap (set, get_value_handle (expr));
- set->length--;
- prev = NULL;
- for (node = set->head;
- node != NULL;
- prev = node, node = node->next)
+ if (dest != orig)
{
- if (node->expr == expr)
- {
- if (prev == NULL)
- set->head = node->next;
- else
- prev->next= node->next;
+ bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
- if (node == set->tail)
- set->tail = prev;
- pool_free (value_set_node_pool, node);
- return;
+ bitmap_and_into (dest->values, orig->values);
+ bitmap_copy (temp, dest->expressions);
+ EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
+ {
+ tree expr = expression_for_id (i);
+ tree val = get_value_handle (expr);
+ if (!bitmap_bit_p (dest->values, VALUE_HANDLE_ID (val)))
+ bitmap_clear_bit (dest->expressions, i);
}
+ BITMAP_FREE (temp);
}
}
-/* Return true if SET contains the value VAL. */
+/* Subtract all values and expressions contained in ORIG from DEST. */
-static bool
-set_contains_value (value_set_t set, tree val)
+static bitmap_set_t
+bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
{
- /* All constants are in every set. */
- if (is_gimple_min_invariant (val))
- return true;
+ bitmap_set_t result = bitmap_set_new ();
+ bitmap_iterator bi;
+ unsigned int i;
- if (!set || set->length == 0)
- return false;
+ bitmap_and_compl (result->expressions, dest->expressions,
+ orig->expressions);
+
+ FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
+ {
+ tree expr = expression_for_id (i);
+ tree val = get_value_handle (expr);
+ bitmap_set_bit (result->values, VALUE_HANDLE_ID (val));
+ }
- return value_exists_in_set_bitmap (set, val);
+ return result;
}
-/* Return true if bitmapped set SET contains the expression EXPR. */
-static bool
-bitmap_set_contains (bitmap_set_t set, tree expr)
+/* Subtract all the values in bitmap set B from bitmap set A. */
+
+static void
+bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
{
- /* All constants are in every set. */
- if (is_gimple_min_invariant (get_value_handle (expr)))
- return true;
+ unsigned int i;
+ bitmap_iterator bi;
+ bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
- /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
- if (TREE_CODE (expr) != SSA_NAME)
- return false;
- return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
+ bitmap_copy (temp, a->expressions);
+ EXECUTE_IF_SET_IN_BITMAP (temp, 0, i, bi)
+ {
+ tree expr = expression_for_id (i);
+ if (bitmap_set_contains_value (b, get_value_handle (expr)))
+ bitmap_remove_from_set (a, expr);
+ }
+ BITMAP_FREE (temp);
}
static bool
bitmap_set_contains_value (bitmap_set_t set, tree val)
{
- if (is_gimple_min_invariant (val))
+ if (constant_expr_p (val))
return true;
+
+ if (!set || bitmap_empty_p (set->expressions))
+ return false;
+
return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
}
+static inline bool
+bitmap_set_contains_expr (bitmap_set_t set, tree expr)
+{
+ return bitmap_bit_p (set->expressions, get_expression_id (expr));
+}
+
/* Replace an instance of value LOOKFOR with expression EXPR in SET. */
static void
bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
{
- value_set_t exprset;
- value_set_node_t node;
- if (is_gimple_min_invariant (lookfor))
+ bitmap_set_t exprset;
+ unsigned int i;
+ bitmap_iterator bi;
+
+ if (constant_expr_p (lookfor))
return;
+
if (!bitmap_set_contains_value (set, lookfor))
return;
significant lose for some cases, we can choose which set to walk
based on the set size. */
exprset = VALUE_HANDLE_EXPR_SET (lookfor);
- for (node = exprset->head; node; node = node->next)
+ FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
{
- if (TREE_CODE (node->expr) == SSA_NAME)
+ if (bitmap_bit_p (set->expressions, i))
{
- if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
- {
- bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
- bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
- return;
- }
+ bitmap_clear_bit (set->expressions, i);
+ bitmap_set_bit (set->expressions, get_expression_id (expr));
+ return;
}
}
}
-/* Subtract bitmapped set B from value set A, and return the new set. */
-
-static value_set_t
-bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
- bool indexed)
-{
- value_set_t ret = set_new (indexed);
- value_set_node_t node;
- for (node = a->head;
- node;
- node = node->next)
- {
- if (!bitmap_set_contains (b, node->expr))
- insert_into_set (ret, node->expr);
- }
- return ret;
-}
-
-/* Return true if two sets are equal. */
+/* Return true if two bitmap sets are equal. */
static bool
-set_equal (value_set_t a, value_set_t b)
+bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
{
- value_set_node_t node;
-
- if (a->length != b->length)
- return false;
- for (node = a->head;
- node;
- node = node->next)
- {
- if (!set_contains_value (b, get_value_handle (node->expr)))
- return false;
- }
- return true;
+ return bitmap_equal_p (a->values, b->values);
}
/* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
{
tree val = get_value_handle (expr);
+
if (bitmap_set_contains_value (set, val))
bitmap_set_replace_value (set, val, expr);
else
{
tree val = get_value_handle (expr);
- if (is_gimple_min_invariant (val))
+ if (constant_expr_p (val))
return;
if (!bitmap_set_contains_value (set, val))
bitmap_insert_into_set (set, expr);
}
-/* Insert the value for EXPR into SET, if it doesn't exist already. */
-
-static void
-value_insert_into_set (value_set_t set, tree expr)
-{
- tree val = get_value_handle (expr);
-
- /* Constant and invariant values exist everywhere, and thus,
- actually keeping them in the sets is pointless. */
- if (is_gimple_min_invariant (val))
- return;
-
- if (!set_contains_value (set, val))
- insert_into_set (set, expr);
-}
-
-
/* Print out SET to OUTFILE. */
static void
-bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
- const char *setname, int blockindex)
+print_bitmap_set (FILE *outfile, bitmap_set_t set,
+ const char *setname, int blockindex)
{
fprintf (outfile, "%s[%d] := { ", setname, blockindex);
if (set)
unsigned i;
bitmap_iterator bi;
- EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
+ FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
{
+ tree expr = expression_for_id (i);
+
if (!first)
fprintf (outfile, ", ");
first = false;
- print_generic_expr (outfile, ssa_name (i), 0);
+ print_generic_expr (outfile, expr, 0);
fprintf (outfile, " (");
- print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
+ print_generic_expr (outfile, get_value_handle (expr), 0);
fprintf (outfile, ") ");
}
}
fprintf (outfile, " }\n");
}
-/* Print out the value_set SET to OUTFILE. */
-
-static void
-print_value_set (FILE *outfile, value_set_t set,
- const char *setname, int blockindex)
-{
- value_set_node_t node;
- fprintf (outfile, "%s[%d] := { ", setname, blockindex);
- if (set)
- {
- for (node = set->head;
- node;
- node = node->next)
- {
- print_generic_expr (outfile, node->expr, 0);
- fprintf (outfile, " (");
- print_generic_expr (outfile, get_value_handle (node->expr), 0);
- fprintf (outfile, ") ");
-
- if (node->next)
- fprintf (outfile, ", ");
- }
- }
+void debug_bitmap_set (bitmap_set_t);
- fprintf (outfile, " }\n");
+void
+debug_bitmap_set (bitmap_set_t set)
+{
+ print_bitmap_set (stderr, set, "debug", 0);
}
/* Print out the expressions that have VAL to OUTFILE. */
{
char s[10];
sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
- print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
+ print_bitmap_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
}
}
print_value_expressions (stderr, val);
}
-
-void debug_value_set (value_set_t, const char *, int);
-
-void
-debug_value_set (value_set_t set, const char *setname, int blockindex)
-{
- print_value_set (stderr, set, setname, blockindex);
-}
-
/* Return the folded version of T if T, when folded, is a gimple
min_invariant. Otherwise, return T. */
return t;
}
-/* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
- For example, this can copy a list made of TREE_LIST nodes.
- Allocates the nodes in list_node_pool*/
+/* Make a temporary copy of a CALL_EXPR object NODE. */
static tree
-pool_copy_list (tree list)
+temp_copy_call_expr (tree node)
{
- tree head;
- tree prev, next;
-
- if (list == 0)
- return 0;
- head = (tree) pool_alloc (list_node_pool);
-
- memcpy (head, list, tree_size (list));
- prev = head;
-
- next = TREE_CHAIN (list);
- while (next)
- {
- TREE_CHAIN (prev) = (tree) pool_alloc (list_node_pool);
- memcpy (TREE_CHAIN (prev), next, tree_size (next));
- prev = TREE_CHAIN (prev);
- next = TREE_CHAIN (next);
- }
- return head;
+ return (tree) obstack_copy (&temp_call_expr_obstack, node, tree_size (node));
}
-/* Translate the vuses in the VUSES vector backwards through phi
- nodes, so that they have the value they would have in BLOCK. */
+/* Translate the vuses in the VUSES vector backwards through phi nodes
+ in PHIBLOCK, 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)
+translate_vuses_through_block (VEC (tree, gc) *vuses,
+ basic_block phiblock,
+ basic_block block)
{
tree oldvuse;
VEC(tree, gc) *result = NULL;
for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
{
tree phi = SSA_NAME_DEF_STMT (oldvuse);
- if (TREE_CODE (phi) == PHI_NODE)
+ if (TREE_CODE (phi) == PHI_NODE
+ && bb_for_stmt (phi) == phiblock)
{
edge e = find_edge (block, bb_for_stmt (phi));
if (e)
}
}
}
+
+ /* We avoid creating a new copy of the vuses unless something
+ actually changed, so result can be NULL. */
if (result)
{
sort_vuses (result);
return vuses;
}
+
+/* Like find_leader, but checks for the value existing in SET1 *or*
+ SET2. This is used to avoid making a set consisting of the union
+ of PA_IN and ANTIC_IN during insert. */
+
+static inline tree
+find_leader_in_sets (tree expr, bitmap_set_t set1, bitmap_set_t set2)
+{
+ tree result;
+
+ result = bitmap_find_leader (set1, expr);
+ if (!result && set2)
+ result = bitmap_find_leader (set2, expr);
+ return result;
+}
+
/* 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. */
+ the phis in PRED. SEEN is a bitmap saying which expression we have
+ translated since we started translation of the toplevel expression.
+ Return NULL if we can't find a leader for each part of the
+ translated expression. */
static tree
-phi_translate (tree expr, value_set_t set, basic_block pred,
- basic_block phiblock)
+phi_translate_1 (tree expr, bitmap_set_t set1, bitmap_set_t set2,
+ basic_block pred, basic_block phiblock, bitmap seen)
{
tree phitrans = NULL;
tree oldexpr = expr;
+
if (expr == NULL)
return NULL;
- if (is_gimple_min_invariant (expr))
+ if (constant_expr_p (expr))
return expr;
/* Phi translations of a given expression don't change. */
- if (EXPR_P (expr))
+ if (EXPR_P (expr) || GIMPLE_STMT_P (expr))
{
tree vh;
if (phitrans)
return phitrans;
+ /* Prevent cycles when we have recursively dependent leaders. This
+ can only happen when phi translating the maximal set. */
+ if (seen)
+ {
+ unsigned int expr_id = get_expression_id (expr);
+ if (bitmap_bit_p (seen, expr_id))
+ return NULL;
+ bitmap_set_bit (seen, expr_id);
+ }
+
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
case tcc_expression:
+ return NULL;
+
+ case tcc_vl_exp:
{
if (TREE_CODE (expr) != CALL_EXPR)
return NULL;
else
{
- tree oldop0 = TREE_OPERAND (expr, 0);
- tree oldarglist = TREE_OPERAND (expr, 1);
- tree oldop2 = TREE_OPERAND (expr, 2);
- tree newop0;
- tree newarglist;
- tree newop2 = NULL;
- tree oldwalker;
- tree newwalker;
- tree newexpr;
+ tree oldfn = CALL_EXPR_FN (expr);
+ tree oldsc = CALL_EXPR_STATIC_CHAIN (expr);
+ tree newfn, newsc = NULL;
+ tree newexpr = NULL_TREE;
tree vh = get_value_handle (expr);
- bool listchanged = false;
+ bool invariantarg = false;
+ int i, nargs;
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
- as one value number, because that doesn't make much
- sense, and just breaks the support functions we call,
- which expect TREE_OPERAND (call_expr, 2) to be a
- TREE_LIST. */
-
- newop0 = phi_translate (find_leader (set, oldop0),
- set, pred, phiblock);
- if (newop0 == NULL)
+ newfn = phi_translate_1 (find_leader_in_sets (oldfn, set1, set2),
+ set1, set2, pred, phiblock, seen);
+ if (newfn == NULL)
return NULL;
- if (oldop2)
+ if (newfn != oldfn)
{
- newop2 = phi_translate (find_leader (set, oldop2),
- set, pred, phiblock);
- if (newop2 == NULL)
+ newexpr = temp_copy_call_expr (expr);
+ CALL_EXPR_FN (newexpr) = get_value_handle (newfn);
+ }
+ if (oldsc)
+ {
+ newsc = phi_translate_1 (find_leader_in_sets (oldsc, set1, set2),
+ set1, set2, pred, phiblock, seen);
+ if (newsc == NULL)
return NULL;
+ if (newsc != oldsc)
+ {
+ if (!newexpr)
+ newexpr = temp_copy_call_expr (expr);
+ CALL_EXPR_STATIC_CHAIN (newexpr) = get_value_handle (newsc);
+ }
}
- /* phi translate the argument list piece by piece.
-
- We could actually build the list piece by piece here,
- but it's likely to not be worth the memory we will save,
- unless you have millions of call arguments. */
-
- newarglist = pool_copy_list (oldarglist);
- for (oldwalker = oldarglist, newwalker = newarglist;
- oldwalker && newwalker;
- oldwalker = TREE_CHAIN (oldwalker),
- newwalker = TREE_CHAIN (newwalker))
+ /* phi translate the argument list piece by piece. */
+ nargs = call_expr_nargs (expr);
+ for (i = 0; i < nargs; i++)
{
-
- tree oldval = TREE_VALUE (oldwalker);
+ tree oldval = CALL_EXPR_ARG (expr, i);
tree newval;
if (oldval)
{
it occurs in the argument list. */
if (AGGREGATE_TYPE_P (TREE_TYPE (oldval)))
return NULL;
- newval = phi_translate (find_leader (set, oldval),
- set, pred, phiblock);
+ oldval = find_leader_in_sets (oldval, set1, set2);
+ newval = phi_translate_1 (oldval, set1, set2, pred,
+ phiblock, seen);
if (newval == NULL)
return NULL;
if (newval != oldval)
{
- listchanged = true;
- TREE_VALUE (newwalker) = get_value_handle (newval);
+ invariantarg |= is_gimple_min_invariant (newval);
+ if (!newexpr)
+ newexpr = temp_copy_call_expr (expr);
+ CALL_EXPR_ARG (newexpr, i) = get_value_handle (newval);
}
}
}
- if (listchanged)
- vn_lookup_or_add (newarglist, NULL);
- tvuses = translate_vuses_through_block (vuses, pred);
+ /* In case of new invariant args we might try to fold the call
+ again. */
+ if (invariantarg && !newsc)
+ {
+ tree tmp1 = build_call_array (TREE_TYPE (expr),
+ newfn, call_expr_nargs (newexpr),
+ CALL_EXPR_ARGP (newexpr));
+ tree tmp2 = fold (tmp1);
+ if (tmp2 != tmp1)
+ {
+ STRIP_TYPE_NOPS (tmp2);
+ if (is_gimple_min_invariant (tmp2))
+ return tmp2;
+ }
+ }
+
+ tvuses = translate_vuses_through_block (vuses, phiblock, pred);
+ if (vuses != tvuses && ! newexpr)
+ newexpr = temp_copy_call_expr (expr);
- if (listchanged || (newop0 != oldop0) || (oldop2 != newop2)
- || vuses != tvuses)
+ if (newexpr)
{
- newexpr = (tree) pool_alloc (expression_node_pool);
- memcpy (newexpr, expr, tree_size (expr));
- TREE_OPERAND (newexpr, 0) = newop0 == oldop0 ? oldop0 : get_value_handle (newop0);
- TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist;
- TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
- create_tree_ann (newexpr);
+ newexpr->base.ann = NULL;
vn_lookup_or_add_with_vuses (newexpr, tvuses);
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred, tvuses);
}
+ phi_trans_add (oldexpr, expr, pred, tvuses);
}
}
return expr;
oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
if (oldvuses)
- newvuses = translate_vuses_through_block (oldvuses, pred);
+ newvuses = translate_vuses_through_block (oldvuses, phiblock,
+ pred);
if (oldvuses != newvuses)
vn_lookup_or_add_with_vuses (expr, newvuses);
&& TREE_CODE (expr) != ARRAY_REF)
return NULL;
- newop0 = phi_translate (find_leader (set, oldop0),
- set, pred, phiblock);
+ oldop0 = find_leader_in_sets (oldop0, set1, set2);
+ newop0 = phi_translate_1 (oldop0, set1, set2, pred, phiblock, seen);
if (newop0 == NULL)
return NULL;
if (TREE_CODE (expr) == ARRAY_REF)
{
oldop1 = TREE_OPERAND (expr, 1);
- newop1 = phi_translate (find_leader (set, oldop1),
- set, pred, phiblock);
+ oldop1 = find_leader_in_sets (oldop1, set1, set2);
+ newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
if (newop1 == NULL)
return NULL;
+
oldop2 = TREE_OPERAND (expr, 2);
if (oldop2)
{
- newop2 = phi_translate (find_leader (set, oldop2),
- set, pred, phiblock);
+ oldop2 = find_leader_in_sets (oldop2, set1, set2);
+ newop2 = phi_translate_1 (oldop2, set1, set2, pred, phiblock, seen);
if (newop2 == NULL)
return NULL;
oldop3 = TREE_OPERAND (expr, 3);
if (oldop3)
{
- newop3 = phi_translate (find_leader (set, oldop3),
- set, pred, phiblock);
+ oldop3 = find_leader_in_sets (oldop3, set1, set2);
+ newop3 = phi_translate_1 (oldop3, set1, set2, pred, phiblock, seen);
if (newop3 == NULL)
return NULL;
oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
if (oldvuses)
- newvuses = translate_vuses_through_block (oldvuses, pred);
+ newvuses = translate_vuses_through_block (oldvuses, phiblock,
+ pred);
if (newop0 != oldop0 || newvuses != oldvuses
|| newop1 != oldop1
{
tree t;
- newexpr = pool_alloc (reference_node_pool);
+ newexpr = (tree) pool_alloc (reference_node_pool);
memcpy (newexpr, expr, tree_size (expr));
TREE_OPERAND (newexpr, 0) = get_value_handle (newop0);
if (TREE_CODE (expr) == ARRAY_REF)
}
else
{
- create_tree_ann (newexpr);
+ newexpr->base.ann = NULL;
vn_lookup_or_add_with_vuses (newexpr, newvuses);
}
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred, newvuses);
}
+ phi_trans_add (oldexpr, expr, pred, newvuses);
}
return expr;
break;
case tcc_comparison:
{
tree oldop1 = TREE_OPERAND (expr, 0);
+ tree oldval1 = oldop1;
tree oldop2 = TREE_OPERAND (expr, 1);
+ tree oldval2 = oldop2;
tree newop1;
tree newop2;
tree newexpr;
- newop1 = phi_translate (find_leader (set, oldop1),
- set, pred, phiblock);
+ oldop1 = find_leader_in_sets (oldop1, set1, set2);
+ newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
if (newop1 == NULL)
return NULL;
- newop2 = phi_translate (find_leader (set, oldop2),
- set, pred, phiblock);
+
+ oldop2 = find_leader_in_sets (oldop2, set1, set2);
+ newop2 = phi_translate_1 (oldop2, set1, set2, pred, phiblock, seen);
if (newop2 == NULL)
return NULL;
if (newop1 != oldop1 || newop2 != oldop2)
tree t;
newexpr = (tree) pool_alloc (binary_node_pool);
memcpy (newexpr, expr, tree_size (expr));
- TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
- TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
+ TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldval1 : get_value_handle (newop1);
+ TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldval2 : get_value_handle (newop2);
t = fully_constant_expression (newexpr);
if (t != newexpr)
{
}
else
{
- create_tree_ann (newexpr);
- vn_lookup_or_add (newexpr, NULL);
+ newexpr->base.ann = NULL;
+ vn_lookup_or_add (newexpr);
}
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred, NULL);
}
+ phi_trans_add (oldexpr, expr, pred, NULL);
}
return expr;
tree newop1;
tree newexpr;
- newop1 = phi_translate (find_leader (set, oldop1),
- set, pred, phiblock);
+ oldop1 = find_leader_in_sets (oldop1, set1, set2);
+ newop1 = phi_translate_1 (oldop1, set1, set2, pred, phiblock, seen);
if (newop1 == NULL)
return NULL;
if (newop1 != oldop1)
}
else
{
- create_tree_ann (newexpr);
- vn_lookup_or_add (newexpr, NULL);
+ newexpr->base.ann = NULL;
+ vn_lookup_or_add (newexpr);
}
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred, NULL);
}
+ phi_trans_add (oldexpr, expr, pred, NULL);
}
return expr;
{
tree phi = NULL;
edge e;
+ tree def_stmt;
gcc_assert (TREE_CODE (expr) == SSA_NAME);
- if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
- phi = SSA_NAME_DEF_STMT (expr);
+
+ def_stmt = SSA_NAME_DEF_STMT (expr);
+ if (TREE_CODE (def_stmt) == PHI_NODE
+ && bb_for_stmt (def_stmt) == phiblock)
+ phi = def_stmt;
else
return expr;
e = find_edge (pred, bb_for_stmt (phi));
if (e)
{
- if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
+ tree val;
+ tree def = PHI_ARG_DEF (phi, e->dest_idx);
+
+ if (is_gimple_min_invariant (def))
+ return def;
+
+ if (is_undefined_value (def))
return NULL;
- vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
- return PHI_ARG_DEF (phi, e->dest_idx);
+
+ val = get_value_handle (def);
+ gcc_assert (val);
+ return def;
}
}
return expr;
}
}
-/* For each expression in SET, translate the value handles through phi nodes
- in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
- expressions in DEST. */
+/* 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. */
+
+static tree
+phi_translate (tree expr, bitmap_set_t set1, bitmap_set_t set2,
+ basic_block pred, basic_block phiblock)
+{
+ bitmap_clear (seen_during_translate);
+ return phi_translate_1 (expr, set1, set2, pred, phiblock,
+ seen_during_translate);
+}
+
+/* For each expression in SET, translate the value handles through phi nodes
+ in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
+ expressions in DEST. */
static void
-phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
+phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
basic_block phiblock)
{
- value_set_node_t node;
- for (node = set->head;
- node;
- node = node->next)
+ VEC (tree, heap) *exprs;
+ tree expr;
+ int i;
+
+ if (!phi_nodes (phiblock))
{
- tree translated;
+ bitmap_set_copy (dest, set);
+ return;
+ }
- translated = phi_translate (node->expr, set, pred, phiblock);
+ exprs = sorted_array_from_bitmap_set (set);
+ for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
+ {
+ tree translated;
+ translated = phi_translate (expr, set, NULL, 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. */
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);
+ phi_trans_add (expr, translated, pred, vuses);
}
if (translated != NULL)
- value_insert_into_set (dest, translated);
+ bitmap_value_insert_into_set (dest, translated);
}
+ VEC_free (tree, heap, exprs);
}
/* Find the leader for a value (i.e., the name representing that
if (val == NULL)
return NULL;
- if (is_gimple_min_invariant (val))
+ if (constant_expr_p (val))
return val;
+
if (bitmap_set_contains_value (set, val))
{
/* Rather than walk the entire bitmap of expressions, and see
than walking the bitmap.
If this is somehow a significant lose for some cases, we can
choose which set to walk based on which set is smaller. */
- value_set_t exprset;
- value_set_node_t node;
- exprset = VALUE_HANDLE_EXPR_SET (val);
- for (node = exprset->head; node; node = node->next)
- {
- if (TREE_CODE (node->expr) == SSA_NAME)
- {
- if (bitmap_bit_p (set->expressions,
- SSA_NAME_VERSION (node->expr)))
- return node->expr;
- }
- }
- }
- return NULL;
-}
-
-
-/* Find the leader for a value (i.e., the name representing that
- value) in a given set, and return it. Return NULL if no leader is
- found. */
-
-static tree
-find_leader (value_set_t set, tree val)
-{
- value_set_node_t node;
-
- if (val == NULL)
- return NULL;
-
- /* Constants represent themselves. */
- if (is_gimple_min_invariant (val))
- return val;
-
- if (set->length == 0)
- return NULL;
+ unsigned int i;
+ bitmap_iterator bi;
+ bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
- if (value_exists_in_set_bitmap (set, val))
- {
- for (node = set->head;
- node;
- node = node->next)
- {
- if (get_value_handle (node->expr) == val)
- return node->expr;
- }
+ EXECUTE_IF_AND_IN_BITMAP (exprset->expressions,
+ set->expressions, 0, i, bi)
+ return expression_for_id (i);
}
-
- 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. */
+/* Determine if VALUE, a memory operation, is ANTIC_IN at the top of
+ BLOCK by seeing if it is not killed in the block. Note that we are
+ only determining whether there is a store that kills it. Because
+ of the order in which clean iterates over values, we are guaranteed
+ that altered operands will have caused us to be eliminated from the
+ ANTIC_IN set already. */
static bool
-vuses_dies_in_block_x (VEC (tree, gc) *vuses, basic_block block)
+value_dies_in_block_x (tree vh, basic_block block)
{
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++)
{
- /* Any places where this is too conservative, are places
- where we created a new version and shouldn't have. */
+ tree def = SSA_NAME_DEF_STMT (vuse);
- if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse))
- || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION (vuse)))
- return true;
+ if (bb_for_stmt (def) != block)
+ continue;
+ if (TREE_CODE (def) == PHI_NODE)
+ continue;
+ 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.
+/* Determine if the expression EXPR is valid in SET1 U SET2.
+ ONLY SET2 CAN BE NULL.
+ 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.
+ For loads/calls, we also see if the vuses are killed in this block.
NB: We never should run into a case where we have SSA_NAME +
- SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
+ SSA_NAME or SSA_NAME + value. The sets valid_in_sets is called on,
the ANTIC sets, will only ever have SSA_NAME's or value expressions
(IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
+#define union_contains_value(SET1, SET2, VAL) \
+ (bitmap_set_contains_value ((SET1), (VAL)) \
+ || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
+
static bool
-valid_in_set (value_set_t set, tree expr, basic_block block)
+valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree expr,
+ basic_block block)
{
tree vh = get_value_handle (expr);
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
tree op1 = TREE_OPERAND (expr, 0);
tree op2 = TREE_OPERAND (expr, 1);
- return set_contains_value (set, op1) && set_contains_value (set, op2);
+
+ return union_contains_value (set1, set2, op1)
+ && union_contains_value (set1, set2, op2);
}
case tcc_unary:
{
tree op1 = TREE_OPERAND (expr, 0);
- return set_contains_value (set, op1);
+ return union_contains_value (set1, set2, op1);
}
case tcc_expression:
+ return false;
+
+ case tcc_vl_exp:
{
if (TREE_CODE (expr) == CALL_EXPR)
{
- tree op0 = TREE_OPERAND (expr, 0);
- tree arglist = TREE_OPERAND (expr, 1);
- tree op2 = TREE_OPERAND (expr, 2);
-
- /* Check the non-list operands first. */
- if (!set_contains_value (set, op0)
- || (op2 && !set_contains_value (set, op2)))
+ tree fn = CALL_EXPR_FN (expr);
+ tree sc = CALL_EXPR_STATIC_CHAIN (expr);
+ tree arg;
+ call_expr_arg_iterator iter;
+
+ /* Check the non-argument operands first. */
+ if (!union_contains_value (set1, set2, fn)
+ || (sc && !union_contains_value (set1, set2, sc)))
return false;
/* Now check the operands. */
- for (; arglist; arglist = TREE_CHAIN (arglist))
+ FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
{
- if (!set_contains_value (set, TREE_VALUE (arglist)))
+ if (!union_contains_value (set1, set2, arg))
return false;
}
- return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
+ return !value_dies_in_block_x (vh, block);
}
return false;
}
{
if (TREE_CODE (expr) == INDIRECT_REF
|| TREE_CODE (expr) == COMPONENT_REF
- || TREE_CODE (expr) == ARRAY_REF)
+ || TREE_CODE (expr) == ARRAY_REF)
{
tree op0 = TREE_OPERAND (expr, 0);
gcc_assert (is_gimple_min_invariant (op0)
|| TREE_CODE (op0) == VALUE_HANDLE);
- if (!set_contains_value (set, op0))
+ if (!union_contains_value (set1, set2, op0))
return false;
if (TREE_CODE (expr) == ARRAY_REF)
{
tree op2 = TREE_OPERAND (expr, 2);
tree op3 = TREE_OPERAND (expr, 3);
gcc_assert (is_gimple_min_invariant (op1)
- || TREE_CODE (op1) == VALUE_HANDLE);
- if (!set_contains_value (set, op1))
+ || TREE_CODE (op1) == VALUE_HANDLE);
+ if (!union_contains_value (set1, set2, op1))
return false;
gcc_assert (!op2 || is_gimple_min_invariant (op2)
- || TREE_CODE (op2) == VALUE_HANDLE);
+ || TREE_CODE (op2) == VALUE_HANDLE);
if (op2
- && !set_contains_value (set, op2))
+ && !union_contains_value (set1, set2, op2))
return false;
gcc_assert (!op3 || is_gimple_min_invariant (op3)
- || TREE_CODE (op3) == VALUE_HANDLE);
+ || TREE_CODE (op3) == VALUE_HANDLE);
if (op3
- && !set_contains_value (set, op3))
+ && !union_contains_value (set1, set2, op3))
return false;
}
- return set_contains_value (ANTIC_SAFE_LOADS (block),
- vh)
- || !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
- block);
+ return !value_dies_in_block_x (vh, block);
}
}
return false;
case tcc_exceptional:
- gcc_assert (TREE_CODE (expr) == SSA_NAME);
- return true;
+ {
+ gcc_assert (TREE_CODE (expr) == SSA_NAME);
+ return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
+ }
case tcc_declaration:
- return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
+ return !value_dies_in_block_x (vh, block);
default:
/* No other cases should be encountered. */
}
}
+/* Clean the set of expressions that are no longer valid in SET1 or
+ SET2. This means expressions that are made up of values we have no
+ leaders for in SET1 or SET2. This version is used for partial
+ anticipation, which means it is not valid in either ANTIC_IN or
+ PA_IN. */
+
+static void
+dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
+{
+ VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (set1);
+ tree expr;
+ int i;
+
+ for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
+ {
+ if (!valid_in_sets (set1, set2, expr, block))
+ bitmap_remove_from_set (set1, expr);
+ }
+ VEC_free (tree, heap, exprs);
+}
+
/* Clean the set of expressions that are no longer valid in SET. This
means expressions that are made up of values we have no leaders for
in SET. */
static void
-clean (value_set_t set, basic_block block)
+clean (bitmap_set_t set, basic_block block)
{
- value_set_node_t node;
- value_set_node_t next;
- node = set->head;
- while (node)
+ VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (set);
+ tree expr;
+ int i;
+
+ for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
{
- next = node->next;
- if (!valid_in_set (set, node->expr, block))
- set_remove (set, node->expr);
- node = next;
+ if (!valid_in_sets (set, NULL, expr, block))
+ bitmap_remove_from_set (set, expr);
}
+ VEC_free (tree, heap, exprs);
}
static sbitmap has_abnormal_preds;
+/* List of blocks that may have changed during ANTIC computation and
+ thus need to be iterated over. */
+
+static sbitmap changed_blocks;
+
+/* Decide whether to defer a block for a later iteration, or PHI
+ translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
+ should defer the block, and true if we processed it. */
+
+static bool
+defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
+ basic_block block, basic_block phiblock)
+{
+ if (!BB_VISITED (phiblock))
+ {
+ SET_BIT (changed_blocks, block->index);
+ BB_VISITED (block) = 0;
+ BB_DEFERRED (block) = 1;
+ return false;
+ }
+ else
+ phi_translate_set (dest, source, block, phiblock);
+ return true;
+}
+
/* Compute the ANTIC set for BLOCK.
If succs(BLOCK) > 1 then
ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
-
- XXX: It would be nice to either write a set_clear, and use it for
- ANTIC_OUT, or to mark the antic_out set as deleted at the end
- of this routine, so that the pool can hand the same memory back out
- again for the next ANTIC_OUT. */
+*/
static bool
compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
{
- basic_block son;
bool changed = false;
- value_set_t S, old, ANTIC_OUT;
- value_set_node_t node;
+ bitmap_set_t S, old, ANTIC_OUT;
+ bitmap_iterator bi;
+ unsigned int bii;
+ edge e;
+ edge_iterator ei;
- ANTIC_OUT = S = NULL;
+ old = ANTIC_OUT = S = NULL;
+ BB_VISITED (block) = 1;
/* If any edges from predecessors are abnormal, antic_in is empty,
so do nothing. */
if (block_has_abnormal_pred_edge)
goto maybe_dump_sets;
- old = set_new (false);
- set_copy (old, ANTIC_IN (block));
- ANTIC_OUT = set_new (true);
+ old = ANTIC_IN (block);
+ ANTIC_OUT = bitmap_set_new ();
/* If the block has no successors, ANTIC_OUT is empty. */
if (EDGE_COUNT (block->succs) == 0)
translate through. */
else if (single_succ_p (block))
{
- phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)),
- block, single_succ (block));
+ basic_block succ_bb = single_succ (block);
+
+ /* We trade iterations of the dataflow equations for having to
+ phi translate the maximal set, which is incredibly slow
+ (since the maximal set often has 300+ members, even when you
+ have a small number of blocks).
+ Basically, we defer the computation of ANTIC for this block
+ until we have processed it's successor, which will inevitably
+ have a *much* smaller set of values to phi translate once
+ clean has been run on it.
+ The cost of doing this is that we technically perform more
+ iterations, however, they are lower cost iterations.
+
+ Timings for PRE on tramp3d-v4:
+ without maximal set fix: 11 seconds
+ with maximal set fix/without deferring: 26 seconds
+ with maximal set fix/with deferring: 11 seconds
+ */
+
+ if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
+ block, succ_bb))
+ {
+ changed = true;
+ goto maybe_dump_sets;
+ }
}
/* If we have multiple successors, we take the intersection of all of
- them. */
+ them. Note that in the case of loop exit phi nodes, we may have
+ phis to translate through. */
else
{
VEC(basic_block, heap) * worklist;
- edge e;
size_t i;
basic_block bprime, first;
- edge_iterator ei;
worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
FOR_EACH_EDGE (e, ei, block->succs)
VEC_quick_push (basic_block, worklist, e->dest);
first = VEC_index (basic_block, worklist, 0);
- set_copy (ANTIC_OUT, ANTIC_IN (first));
+
+ 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);
+ }
+ else
+ {
+ if (!BB_VISITED (first))
+ bitmap_set_copy (ANTIC_OUT, maximal_set);
+ else
+ bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
+ }
for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
{
- node = ANTIC_OUT->head;
- while (node)
+ if (phi_nodes (bprime))
{
- 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);
- node = next;
+ 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
+ {
+ if (!BB_VISITED (bprime))
+ bitmap_set_and (ANTIC_OUT, maximal_set);
+ else
+ bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
}
}
VEC_free (basic_block, heap, worklist);
}
/* Generate ANTIC_OUT - TMP_GEN. */
- S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
+ S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
- /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
- ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block),
- TMP_GEN (block),
- true);
+ /* Start ANTIC_IN with EXP_GEN - TMP_GEN. */
+ ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
+ TMP_GEN (block));
/* Then union in the ANTIC_OUT - TMP_GEN values,
to get ANTIC_OUT U EXP_GEN - TMP_GEN */
- for (node = S->head; node; node = node->next)
- value_insert_into_set (ANTIC_IN (block), node->expr);
+ FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
+ bitmap_value_insert_into_set (ANTIC_IN (block),
+ expression_for_id (bii));
clean (ANTIC_IN (block), block);
- if (!set_equal (old, ANTIC_IN (block)))
- changed = true;
+
+ /* !old->expressions can happen when we deferred a block. */
+ if (!old->expressions || !bitmap_set_equal (old, ANTIC_IN (block)))
+ {
+ changed = true;
+ SET_BIT (changed_blocks, block->index);
+ FOR_EACH_EDGE (e, ei, block->preds)
+ SET_BIT (changed_blocks, e->src->index);
+ }
+ else
+ RESET_BIT (changed_blocks, block->index);
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (ANTIC_OUT)
- print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
-
- if (ANTIC_SAFE_LOADS (block))
- print_value_set (dump_file, ANTIC_SAFE_LOADS (block),
- "ANTIC_SAFE_LOADS", block->index);
- print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
+ if (!BB_DEFERRED (block) || BB_VISITED (block))
+ {
+ if (ANTIC_OUT)
+ print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
- if (S)
- print_value_set (dump_file, S, "S", block->index);
- }
+ print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
+ block->index);
- for (son = first_dom_son (CDI_POST_DOMINATORS, block);
- son;
- son = next_dom_son (CDI_POST_DOMINATORS, son))
- {
- changed |= compute_antic_aux (son,
- TEST_BIT (has_abnormal_preds, son->index));
+ if (S)
+ print_bitmap_set (dump_file, S, "S", block->index);
+ }
+ else
+ {
+ fprintf (dump_file,
+ "Block %d was deferred for a future iteration.\n",
+ block->index);
+ }
}
+ if (old)
+ bitmap_set_free (old);
+ if (S)
+ bitmap_set_free (S);
+ if (ANTIC_OUT)
+ bitmap_set_free (ANTIC_OUT);
return changed;
}
-/* Compute ANTIC sets. */
-
-static void
-compute_antic (void)
-{
- bool changed = true;
- int num_iterations = 0;
- basic_block block;
-
- /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
- We pre-build the map of blocks with incoming abnormal edges here. */
- has_abnormal_preds = sbitmap_alloc (last_basic_block);
- sbitmap_zero (has_abnormal_preds);
- FOR_EACH_BB (block)
- {
- edge_iterator ei;
- edge e;
-
- FOR_EACH_EDGE (e, ei, block->preds)
- if (e->flags & EDGE_ABNORMAL)
- {
- SET_BIT (has_abnormal_preds, block->index);
- break;
- }
-
- /* While we are here, give empty ANTIC_IN sets to each block. */
- ANTIC_IN (block) = set_new (true);
- }
- /* At the exit block we anticipate nothing. */
- ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
-
- while (changed)
- {
- num_iterations++;
- changed = false;
- changed = compute_antic_aux (EXIT_BLOCK_PTR, false);
- }
+/* Compute PARTIAL_ANTIC for BLOCK.
- sbitmap_free (has_abnormal_preds);
+ If succs(BLOCK) > 1 then
+ PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
+ in ANTIC_OUT for all succ(BLOCK)
+ else if succs(BLOCK) == 1 then
+ PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
- if (dump_file && (dump_flags & TDF_STATS))
- fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
-}
+ PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
+ - ANTIC_IN[BLOCK])
-/* Print the names represented by the bitmap NAMES, to the file OUT. */
-static void
-dump_bitmap_of_names (FILE *out, bitmap names)
+*/
+static bool
+compute_partial_antic_aux (basic_block block,
+ bool block_has_abnormal_pred_edge)
{
- 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");
-}
+ bool changed = false;
+ bitmap_set_t old_PA_IN;
+ bitmap_set_t PA_OUT;
+ edge e;
+ edge_iterator ei;
- /* 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.
+ old_PA_IN = PA_OUT = NULL;
- 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. */
+ /* If any edges from predecessors are abnormal, antic_in is empty,
+ so do nothing. */
+ if (block_has_abnormal_pred_edge)
+ goto maybe_dump_sets;
-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;
+ old_PA_IN = PA_IN (block);
+ PA_OUT = bitmap_set_new ();
- FOR_EACH_BB (bb)
+ /* If the block has no successors, ANTIC_OUT is empty. */
+ if (EDGE_COUNT (block->succs) == 0)
+ ;
+ /* If we have one successor, we could have some phi nodes to
+ translate through. Note that we can't phi translate across DFS
+ back edges in partial antic, because it uses a union operation on
+ the successors. For recurrences like IV's, we will end up
+ generating a new value in the set on each go around (i + 3 (VH.1)
+ VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever. */
+ else if (single_succ_p (block))
{
- for (phi = phi_nodes (bb);
- phi;
- phi = PHI_CHAIN (phi))
- if (!is_gimple_reg (PHI_RESULT (phi)))
- VEC_safe_push (tree, heap, phis, phi);
+ basic_block succ = single_succ (block);
+ if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
+ phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
}
-
- while (changed)
+ /* If we have multiple successors, we take the union of all of
+ them. */
+ else
{
- changed = false;
+ VEC(basic_block, heap) * worklist;
+ size_t i;
+ basic_block bprime;
- for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
+ worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
+ FOR_EACH_EDGE (e, ei, block->succs)
{
- 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)
+ if (e->flags & EDGE_DFS_BACK)
+ continue;
+ VEC_quick_push (basic_block, worklist, e->dest);
+ }
+ if (VEC_length (basic_block, worklist) > 0)
+ {
+ for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
{
- tree use = USE_FROM_PTR (usep);
- bitmap usebitmap = get_representative (vuse_names,
- SSA_NAME_VERSION (use));
- if (usebitmap != NULL)
+ unsigned int i;
+ bitmap_iterator bi;
+
+ FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
+ bitmap_value_insert_into_set (PA_OUT,
+ expression_for_id (i));
+ if (phi_nodes (bprime))
{
- changed |= bitmap_ior_into (vuse_names[ver],
- usebitmap);
+ bitmap_set_t pa_in = bitmap_set_new ();
+ phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
+ FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
+ bitmap_value_insert_into_set (PA_OUT,
+ expression_for_id (i));
+ bitmap_set_free (pa_in);
}
else
- {
- changed |= !bitmap_bit_p (vuse_names[ver],
- SSA_NAME_VERSION (use));
- if (changed)
- bitmap_set_bit (vuse_names[ver],
- SSA_NAME_VERSION (use));
- }
+ FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
+ bitmap_value_insert_into_set (PA_OUT,
+ expression_for_id (i));
}
}
+ VEC_free (basic_block, heap, worklist);
}
- 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);
-}
+ /* PA_IN starts with PA_OUT - TMP_GEN.
+ Then we subtract things from ANTIC_IN. */
+ PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
-/* Compute reaching vuses and antic safe loads. RVUSE computation is
- 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.
+ /* For partial antic, we want to put back in the phi results, since
+ we will properly avoid making them partially antic over backedges. */
+ bitmap_ior_into (PA_IN (block)->values, PHI_GEN (block)->values);
+ bitmap_ior_into (PA_IN (block)->expressions, PHI_GEN (block)->expressions);
- ANTIC_SAFE_LOADS are those loads that actually occur before any kill to
- their vuses in the block,and thus, are safe at the top of the
- block.
+ /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
+ bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
- An example:
+ dependent_clean (PA_IN (block), ANTIC_IN (block), block);
- <block begin>
- b = *a
- *a = 9
- <block end>
+ if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
+ {
+ changed = true;
+ SET_BIT (changed_blocks, block->index);
+ FOR_EACH_EDGE (e, ei, block->preds)
+ SET_BIT (changed_blocks, e->src->index);
+ }
+ else
+ RESET_BIT (changed_blocks, block->index);
- b = *a is an antic safe load because it still safe to consider it
- ANTIC at the top of the block.
+ maybe_dump_sets:
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ if (PA_OUT)
+ print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
+
+ print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
+ }
+ if (old_PA_IN)
+ bitmap_set_free (old_PA_IN);
+ if (PA_OUT)
+ bitmap_set_free (PA_OUT);
+ return changed;
+}
- We currently compute a conservative approximation to
- ANTIC_SAFE_LOADS. We compute those loads that occur before *any*
- stores in the block. This is not because it is difficult to
- compute the precise answer, but because it is expensive. More
- testing is necessary to determine whether it is worth computing the
- precise answer. */
+/* Compute ANTIC and partial ANTIC sets. */
static void
-compute_rvuse_and_antic_safe (void)
+compute_antic (void)
{
-
- size_t i;
- tree phi;
- basic_block bb;
- int *postorder;
bool changed = true;
- unsigned int *first_store_uid;
-
- first_store_uid = xcalloc (n_basic_blocks, sizeof (unsigned int));
-
- 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);
- ANTIC_SAFE_LOADS (bb) = NULL;
- }
-
- /* 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));
- }
+ int num_iterations = 0;
+ basic_block block;
+ int i;
- /* Compute local sets for reaching vuses.
- GEN(block) = generated in block and not locally killed.
- KILL(block) = set of vuses killed in block.
- */
+ /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
+ We pre-build the map of blocks with incoming abnormal edges here. */
+ has_abnormal_preds = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (has_abnormal_preds);
- FOR_EACH_BB (bb)
+ FOR_EACH_BB (block)
{
- block_stmt_iterator bsi;
- ssa_op_iter iter;
- def_operand_p defp;
- use_operand_p usep;
+ edge_iterator ei;
+ edge e;
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ FOR_EACH_EDGE (e, ei, block->preds)
{
- tree stmt = bsi_stmt (bsi);
-
- if (first_store_uid[bb->index] == 0
- && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYUSE | SSA_OP_VMAYDEF
- | SSA_OP_VMUSTDEF | SSA_OP_VMUSTKILL))
- {
- first_store_uid[bb->index] = stmt_ann (stmt)->uid;
- }
-
-
- 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)
+ e->flags &= ~EDGE_DFS_BACK;
+ if (e->flags & EDGE_ABNORMAL)
{
- tree def = DEF_FROM_PTR (defp);
- bitmap_set_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (def));
+ SET_BIT (has_abnormal_preds, block->index);
+ break;
}
}
- }
- 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));
- }
- }
+ BB_VISITED (block) = 0;
+ BB_DEFERRED (block) = 0;
+ /* While we are here, give empty ANTIC_IN sets to each block. */
+ ANTIC_IN (block) = bitmap_set_new ();
+ PA_IN (block) = bitmap_set_new ();
}
- /* 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 = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
- pre_and_rev_post_order_compute (NULL, postorder, false);
+ /* At the exit block we anticipate nothing. */
+ ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
+ BB_VISITED (EXIT_BLOCK_PTR) = 1;
+ PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
- changed = true;
+ changed_blocks = sbitmap_alloc (last_basic_block + 1);
+ sbitmap_ones (changed_blocks);
while (changed)
{
- int j;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Starting iteration %d\n", num_iterations);
+ num_iterations++;
changed = false;
- for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
+ for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
{
- 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));
+ if (TEST_BIT (changed_blocks, postorder[i]))
+ {
+ basic_block block = BASIC_BLOCK (postorder[i]);
+ changed |= compute_antic_aux (block,
+ TEST_BIT (has_abnormal_preds,
+ block->index));
+ }
}
+ /* Theoretically possible, but *highly* unlikely. */
+ gcc_assert (num_iterations < 50);
}
- 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));
- }
- }
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, "compute_antic required %d iterations\n",
+ num_iterations);
- FOR_EACH_BB (bb)
+ if (do_partial_partial)
{
- value_set_node_t node;
- if (bitmap_empty_p (RVUSE_KILL (bb)))
- continue;
-
- for (node = EXP_GEN (bb)->head; node; node = node->next)
+ sbitmap_ones (changed_blocks);
+ mark_dfs_back_edges ();
+ num_iterations = 0;
+ changed = true;
+ while (changed)
{
- if (REFERENCE_CLASS_P (node->expr))
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Starting iteration %d\n", num_iterations);
+ num_iterations++;
+ changed = false;
+ for (i = 0; i < last_basic_block - NUM_FIXED_BLOCKS; i++)
{
- tree vh = get_value_handle (node->expr);
- tree maybe = bitmap_find_leader (AVAIL_OUT (bb), vh);
-
- if (maybe)
+ if (TEST_BIT (changed_blocks, postorder[i]))
{
- tree def = SSA_NAME_DEF_STMT (maybe);
-
- if (bb_for_stmt (def) != bb)
- continue;
-
- if (TREE_CODE (def) == PHI_NODE
- || stmt_ann (def)->uid < first_store_uid[bb->index])
- {
- if (ANTIC_SAFE_LOADS (bb) == NULL)
- ANTIC_SAFE_LOADS (bb) = set_new (true);
- value_insert_into_set (ANTIC_SAFE_LOADS (bb),
- node->expr);
- }
+ basic_block block = BASIC_BLOCK (postorder[i]);
+ changed
+ |= compute_partial_antic_aux (block,
+ TEST_BIT (has_abnormal_preds,
+ block->index));
}
}
+ /* Theoretically possible, but *highly* unlikely. */
+ gcc_assert (num_iterations < 50);
}
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, "compute_partial_antic required %d iterations\n",
+ num_iterations);
}
- free (first_store_uid);
+ sbitmap_free (has_abnormal_preds);
+ sbitmap_free (changed_blocks);
}
/* Return true if we can value number the call in STMT. This is true
return false;
}
+/* Return true if OP is an exception handler related operation, such as
+ FILTER_EXPRor EXC_PTR_EXPR. */
+
+static bool
+is_exception_related (tree op)
+{
+ return TREE_CODE (op) == FILTER_EXPR || TREE_CODE (op) == EXC_PTR_EXPR;
+}
+
/* 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)
+ return (UNARY_CLASS_P (op)
+ && !is_exception_related (TREE_OPERAND (op, 0)))
|| BINARY_CLASS_P (op)
|| COMPARISON_CLASS_P (op)
|| REFERENCE_CLASS_P (op)
}
if (TREE_CODE (genop) == VALUE_HANDLE)
- genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
+ {
+ bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (expr);
+ unsigned int firstbit = bitmap_first_set_bit (exprset->expressions);
+ genop = expression_for_id (firstbit);
+ }
switch TREE_CODE (genop)
{
op0 = create_component_ref_by_pieces (block,
TREE_OPERAND (genop, 0),
stmts);
- op1 = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (genop, 1))->head->expr;
+ /* op1 should be a FIELD_DECL, which are represented by
+ themselves. */
+ op1 = TREE_OPERAND (genop, 1);
folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1,
NULL_TREE);
return folded;
it recursively. */
if (genop == NULL)
{
- genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
+ bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (expr);
+ bool handled = false;
+ bitmap_iterator bi;
+ unsigned int i;
- gcc_assert (can_PRE_operation (genop));
- genop = create_expression_by_pieces (block, genop, stmts);
+ /* We will hit cases where we have SSA_NAME's in exprset before
+ other operations, because we may have come up with the SCCVN
+ value before getting to the RHS of the expression. */
+ FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
+ {
+ genop = expression_for_id (i);
+ if (can_PRE_operation (genop))
+ {
+ handled = true;
+ genop = create_expression_by_pieces (block, genop, stmts);
+ break;
+ }
+ }
+ gcc_assert (handled);
}
return genop;
}
-#define NECESSARY(stmt) stmt->common.asm_written_flag
+#define NECESSARY(stmt) stmt->base.asm_written_flag
/* Create an expression in pieces, so that we can handle very complex
expressions that may be ANTIC, but not necessary GIMPLE.
BLOCK is the basic block the expression will be inserted into,
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
- case tcc_expression:
+ case tcc_vl_exp:
{
- tree op0, op2;
- tree arglist;
- tree genop0, genop2;
- tree genarglist;
- tree walker, genwalker;
+ tree fn, sc;
+ tree genfn;
+ int i, nargs;
+ tree *buffer;
gcc_assert (TREE_CODE (expr) == CALL_EXPR);
- genop2 = NULL;
- op0 = TREE_OPERAND (expr, 0);
- arglist = TREE_OPERAND (expr, 1);
- op2 = TREE_OPERAND (expr, 2);
+ fn = CALL_EXPR_FN (expr);
+ sc = CALL_EXPR_STATIC_CHAIN (expr);
- genop0 = find_or_generate_expression (block, op0, stmts);
- genarglist = copy_list (arglist);
- for (walker = arglist, genwalker = genarglist;
- genwalker && walker;
- genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker))
+ genfn = find_or_generate_expression (block, fn, stmts);
+
+ nargs = call_expr_nargs (expr);
+ buffer = (tree*) alloca (nargs * sizeof (tree));
+
+ for (i = 0; i < nargs; i++)
{
- TREE_VALUE (genwalker)
- = find_or_generate_expression (block, TREE_VALUE (walker),
- stmts);
+ tree arg = CALL_EXPR_ARG (expr, i);
+ buffer[i] = find_or_generate_expression (block, arg, stmts);
}
- if (op2)
- genop2 = find_or_generate_expression (block, op2, stmts);
- folded = fold_build3 (TREE_CODE (expr), TREE_TYPE (expr),
- genop0, genarglist, genop2);
+ folded = build_call_array (TREE_TYPE (expr), genfn, nargs, buffer);
+ if (sc)
+ CALL_EXPR_STATIC_CHAIN (folded) =
+ find_or_generate_expression (block, sc, stmts);
+ folded = fold (folded);
break;
-
-
}
break;
case tcc_reference:
We have to call unshare_expr because force_gimple_operand may
modify the tree we pass to it. */
newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
- false, NULL);
+ false, NULL);
/* If we have any intermediate expressions to the value sets, add them
to the value sets and chain them on in the instruction stream. */
for (; !tsi_end_p (tsi); tsi_next (&tsi))
{
tree stmt = tsi_stmt (tsi);
- tree forcedname = TREE_OPERAND (stmt, 0);
- tree forcedexpr = TREE_OPERAND (stmt, 1);
- tree val = vn_lookup_or_add (forcedexpr, NULL);
+ tree forcedname = GIMPLE_STMT_OPERAND (stmt, 0);
+ tree forcedexpr = GIMPLE_STMT_OPERAND (stmt, 1);
+ tree val = vn_lookup_or_add (forcedexpr);
VEC_safe_push (tree, heap, inserted_exprs, stmt);
+ VN_INFO_GET (forcedname)->valnum = forcedname;
vn_add (forcedname, val);
bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
- mark_new_vars_to_rename (stmt);
+ mark_symbols_for_renaming (stmt);
}
tsi = tsi_last (stmts);
tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
temp = pretemp;
add_referenced_var (temp);
- if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
- DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
+ if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE
+ || TREE_CODE (TREE_TYPE (expr)) == VECTOR_TYPE)
+ DECL_GIMPLE_REG_P (temp) = 1;
- newexpr = build2 (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr);
+ newexpr = build_gimple_modify_stmt (temp, newexpr);
name = make_ssa_name (temp, newexpr);
- TREE_OPERAND (newexpr, 0) = name;
+ GIMPLE_STMT_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);
- mark_new_vars_to_rename (newexpr);
+
+ /* All the symbols in NEWEXPR should be put into SSA form. */
+ mark_symbols_for_renaming (newexpr);
/* Add a value handle to the temporary.
The value may already exist in either NEW_SETS, or AVAIL_OUT, because
here. */
v = get_value_handle (expr);
vn_add (name, v);
+ VN_INFO_GET (name)->valnum = name;
+ get_or_alloc_expression_id (name);
bitmap_value_replace_in_set (NEW_SETS (block), name);
bitmap_value_replace_in_set (AVAIL_OUT (block), name);
return name;
}
-/* Insert the to-be-made-available values of NODE for each
+/* Insert the to-be-made-available values of expression EXPRNUM 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,
+insert_into_preds_of_block (basic_block block, unsigned int exprnum,
tree *avail)
{
- tree val = get_value_handle (node->expr);
+ tree expr = expression_for_id (exprnum);
+ tree val = get_value_handle (expr);
edge pred;
bool insertions = false;
bool nophi = false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Found partial redundancy for expression ");
- print_generic_expr (dump_file, node->expr, 0);
+ print_generic_expr (dump_file, expr, 0);
fprintf (dump_file, " (");
print_generic_expr (dump_file, val, 0);
fprintf (dump_file, ")");
/* Make sure we aren't creating an induction variable. */
if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
- && TREE_CODE_CLASS (TREE_CODE (node->expr)) != tcc_reference )
+ && TREE_CODE_CLASS (TREE_CODE (expr)) != tcc_reference )
{
bool firstinsideloop = false;
bool secondinsideloop = false;
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);
+ gcc_assert (!(pred->flags & EDGE_ABNORMAL));
bsi_insert_on_edge (pred, stmts);
avail[bprime->index] = builtexpr;
insertions = true;
temp = prephitemp;
add_referenced_var (temp);
- if (TREE_CODE (type) == COMPLEX_TYPE)
- DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
+
+ if (TREE_CODE (type) == COMPLEX_TYPE
+ || TREE_CODE (type) == VECTOR_TYPE)
+ DECL_GIMPLE_REG_P (temp) = 1;
temp = create_phi_node (temp, block);
NECESSARY (temp) = 0;
+ VN_INFO_GET (PHI_RESULT (temp))->valnum = PHI_RESULT (temp);
+
VEC_safe_push (tree, heap, inserted_exprs, temp);
FOR_EACH_EDGE (pred, ei, block->preds)
add_phi_arg (temp, avail[pred->src->index], pred);
-/* Perform insertion of partially redundant values.
- For BLOCK, do the following:
- 1. Propagate the NEW_SETS of the dominator into the current block.
- If the block has multiple predecessors,
- 2a. Iterate over the ANTIC expressions for the block to see if
- any of them are partially redundant.
- 2b. If so, insert them into the necessary predecessors to make
- the expression fully redundant.
- 2c. Insert a new PHI merging the values of the predecessors.
- 2d. Insert the new PHI, and the new expressions, into the
- NEW_SETS set.
- 3. Recursively call ourselves on the dominator children of BLOCK.
+/* Perform insertion of partially redundant values.
+ For BLOCK, do the following:
+ 1. Propagate the NEW_SETS of the dominator into the current block.
+ If the block has multiple predecessors,
+ 2a. Iterate over the ANTIC expressions for the block to see if
+ any of them are partially redundant.
+ 2b. If so, insert them into the necessary predecessors to make
+ the expression fully redundant.
+ 2c. Insert a new PHI merging the values of the predecessors.
+ 2d. Insert the new PHI, and the new expressions, into the
+ NEW_SETS set.
+ 3. Recursively call ourselves on the dominator children of BLOCK.
+
+ Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
+ do_regular_insertion and do_partial_insertion.
+
+*/
+
+static bool
+do_regular_insertion (basic_block block, basic_block dom)
+{
+ bool new_stuff = false;
+ VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
+ tree expr;
+ int i;
+
+ for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
+ {
+ if (can_PRE_operation (expr) && !AGGREGATE_TYPE_P (TREE_TYPE (expr)))
+ {
+ tree *avail;
+ tree val;
+ bool by_some = false;
+ bool cant_insert = false;
+ bool all_same = true;
+ tree first_s = NULL;
+ edge pred;
+ basic_block bprime;
+ tree eprime = NULL_TREE;
+ edge_iterator ei;
+
+ val = get_value_handle (expr);
+ if (bitmap_set_contains_value (PHI_GEN (block), val))
+ continue;
+ if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Found fully redundant value\n");
+ continue;
+ }
+
+ avail = XCNEWVEC (tree, last_basic_block);
+ FOR_EACH_EDGE (pred, ei, block->preds)
+ {
+ tree vprime;
+ tree edoubleprime;
+
+ /* This can happen in the very weird case
+ that our fake infinite loop edges have caused a
+ critical edge to appear. */
+ if (EDGE_CRITICAL_P (pred))
+ {
+ cant_insert = true;
+ break;
+ }
+ bprime = pred->src;
+ eprime = phi_translate (expr, ANTIC_IN (block), NULL,
+ bprime, block);
+
+ /* eprime will generally only be NULL if the
+ value of the expression, translated
+ through the PHI for this predecessor, is
+ undefined. If that is the case, we can't
+ make the expression fully redundant,
+ because its value is undefined along a
+ predecessor path. We can thus break out
+ early because it doesn't matter what the
+ rest of the results are. */
+ if (eprime == NULL)
+ {
+ cant_insert = true;
+ break;
+ }
+
+ eprime = fully_constant_expression (eprime);
+ vprime = get_value_handle (eprime);
+ gcc_assert (vprime);
+ edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
+ vprime);
+ if (edoubleprime == NULL)
+ {
+ avail[bprime->index] = eprime;
+ all_same = false;
+ }
+ else
+ {
+ avail[bprime->index] = edoubleprime;
+ by_some = true;
+ if (first_s == NULL)
+ first_s = edoubleprime;
+ else if (!operand_equal_p (first_s, edoubleprime,
+ 0))
+ all_same = false;
+ }
+ }
+ /* If we can insert it, it's not the same value
+ already existing along every predecessor, and
+ it's defined by some predecessor, it is
+ partially redundant. */
+ if (!cant_insert && !all_same && by_some)
+ {
+ if (insert_into_preds_of_block (block, get_expression_id (expr),
+ avail))
+ new_stuff = true;
+ }
+ /* If all edges produce the same value and that value is
+ an invariant, then the PHI has the same value on all
+ edges. Note this. */
+ else if (!cant_insert && all_same && eprime
+ && is_gimple_min_invariant (eprime)
+ && !is_gimple_min_invariant (val))
+ {
+ unsigned int j;
+ bitmap_iterator bi;
+
+ bitmap_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
+ FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
+ {
+ tree expr = expression_for_id (j);
+ if (TREE_CODE (expr) == SSA_NAME)
+ {
+ vn_add (expr, eprime);
+ pre_stats.constified++;
+ }
+ }
+ }
+ free (avail);
+ }
+ }
+
+ VEC_free (tree, heap, exprs);
+ return new_stuff;
+}
+
+
+/* Perform insertion for partially anticipatable expressions. There
+ is only one case we will perform insertion for these. This case is
+ if the expression is partially anticipatable, and fully available.
+ In this case, we know that putting it earlier will enable us to
+ remove the later computation. */
+
+
+static bool
+do_partial_partial_insertion (basic_block block, basic_block dom)
+{
+ bool new_stuff = false;
+ VEC (tree, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
+ tree expr;
+ int i;
+
+ for (i = 0; VEC_iterate (tree, exprs, i, expr); i++)
+ {
+ if (can_PRE_operation (expr) && !AGGREGATE_TYPE_P (TREE_TYPE (expr)))
+ {
+ tree *avail;
+ tree val;
+ bool by_all = true;
+ bool cant_insert = false;
+ edge pred;
+ basic_block bprime;
+ tree eprime = NULL_TREE;
+ edge_iterator ei;
+
+ val = get_value_handle (expr);
+ if (bitmap_set_contains_value (PHI_GEN (block), val))
+ continue;
+ if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
+ continue;
+
+ avail = XCNEWVEC (tree, last_basic_block);
+ FOR_EACH_EDGE (pred, ei, block->preds)
+ {
+ tree vprime;
+ tree edoubleprime;
+
+ /* This can happen in the very weird case
+ that our fake infinite loop edges have caused a
+ critical edge to appear. */
+ if (EDGE_CRITICAL_P (pred))
+ {
+ cant_insert = true;
+ break;
+ }
+ bprime = pred->src;
+ eprime = phi_translate (expr, ANTIC_IN (block),
+ PA_IN (block),
+ bprime, block);
+
+ /* eprime will generally only be NULL if the
+ value of the expression, translated
+ through the PHI for this predecessor, is
+ undefined. If that is the case, we can't
+ make the expression fully redundant,
+ because its value is undefined along a
+ predecessor path. We can thus break out
+ early because it doesn't matter what the
+ rest of the results are. */
+ if (eprime == NULL)
+ {
+ cant_insert = true;
+ break;
+ }
+
+ eprime = fully_constant_expression (eprime);
+ vprime = get_value_handle (eprime);
+ gcc_assert (vprime);
+ edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
+ vprime);
+ if (edoubleprime == NULL)
+ {
+ by_all = false;
+ break;
+ }
+ else
+ avail[bprime->index] = edoubleprime;
+
+ }
+
+ /* If we can insert it, it's not the same value
+ already existing along every predecessor, and
+ it's defined by some predecessor, it is
+ partially redundant. */
+ if (!cant_insert && by_all)
+ {
+ pre_stats.pa_insert++;
+ if (insert_into_preds_of_block (block, get_expression_id (expr),
+ avail))
+ new_stuff = true;
+ }
+ free (avail);
+ }
+ }
-*/
+ VEC_free (tree, heap, exprs);
+ return new_stuff;
+}
static bool
insert_aux (basic_block block)
AVAIL_OUT. For both the case of NEW_SETS, the value may be
represented by some non-simple expression here that we want
to replace it with. */
- EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
+ FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
{
- bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
- bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
+ tree expr = expression_for_id (i);
+ bitmap_value_replace_in_set (NEW_SETS (block), expr);
+ bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
}
}
if (!single_pred_p (block))
{
- value_set_node_t node;
- for (node = ANTIC_IN (block)->head;
- node;
- node = node->next)
- {
- if (can_PRE_operation (node->expr)
- && !AGGREGATE_TYPE_P (TREE_TYPE (node->expr)))
- {
- tree *avail;
- tree val;
- bool by_some = false;
- bool cant_insert = false;
- bool all_same = true;
- tree first_s = NULL;
- edge pred;
- basic_block bprime;
- tree eprime = NULL_TREE;
- edge_iterator ei;
-
- val = get_value_handle (node->expr);
- if (bitmap_set_contains_value (PHI_GEN (block), val))
- continue;
- if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Found fully redundant value\n");
- continue;
- }
-
- avail = XCNEWVEC (tree, last_basic_block);
- FOR_EACH_EDGE (pred, ei, block->preds)
- {
- tree vprime;
- tree edoubleprime;
-
- /* This can happen in the very weird case
- that our fake infinite loop edges have caused a
- critical edge to appear. */
- if (EDGE_CRITICAL_P (pred))
- {
- cant_insert = true;
- break;
- }
- bprime = pred->src;
- eprime = phi_translate (node->expr,
- ANTIC_IN (block),
- bprime, block);
-
- /* eprime will generally only be NULL if the
- value of the expression, translated
- through the PHI for this predecessor, is
- undefined. If that is the case, we can't
- make the expression fully redundant,
- because its value is undefined along a
- predecessor path. We can thus break out
- early because it doesn't matter what the
- rest of the results are. */
- if (eprime == NULL)
- {
- cant_insert = true;
- break;
- }
-
- eprime = fully_constant_expression (eprime);
- vprime = get_value_handle (eprime);
- gcc_assert (vprime);
- edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
- vprime);
- if (edoubleprime == NULL)
- {
- avail[bprime->index] = eprime;
- all_same = false;
- }
- else
- {
- avail[bprime->index] = edoubleprime;
- by_some = true;
- if (first_s == NULL)
- first_s = edoubleprime;
- else if (!operand_equal_p (first_s, edoubleprime,
- 0))
- all_same = false;
- }
- }
- /* If we can insert it, it's not the same value
- already existing along every predecessor, and
- it's defined by some predecessor, it is
- partially redundant. */
- if (!cant_insert && !all_same && by_some)
- {
- if (insert_into_preds_of_block (block, node, avail))
- new_stuff = true;
- }
- /* If all edges produce the same value and that value is
- an invariant, then the PHI has the same value on all
- edges. Note this. */
- else if (!cant_insert && all_same && eprime
- && is_gimple_min_invariant (eprime)
- && !is_gimple_min_invariant (val))
- {
- 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);
- pre_stats.constified++;
- }
- }
- }
- free (avail);
- }
- }
+ new_stuff |= do_regular_insertion (block, dom);
+ if (do_partial_partial)
+ new_stuff |= do_partial_partial_insertion (block, dom);
}
}
}
is_undefined_value (tree expr)
{
return (TREE_CODE (expr) == SSA_NAME
- && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
+ && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
/* PARM_DECLs and hard registers are always defined. */
&& 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)
+{
+ if (!in_fre)
+ {
+ if (TREE_CODE (op) == SSA_NAME && is_undefined_value (op))
+ return;
+ 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
EXPR are not the same, associate VAL with VAR. Finally, add VAR to
- S1 and its value handle to S2.
+ S1 and its value handle to S2, and to the maximal set if
+ ADD_TO_MAXIMAL is true.
VUSES represent the virtual use operands associated with EXPR (if
any). */
add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
bitmap_set_t s2)
{
- tree val = vn_lookup_or_add (expr, stmt);
+ tree val;
+ val = vn_lookup_or_add_with_stmt (expr, stmt);
/* VAR and EXPR may be the same when processing statements for which
we are not computing value numbers (e.g., non-assignments, or
if (s1)
bitmap_insert_into_set (s1, var);
+
bitmap_value_insert_into_set (s2, var);
}
+/* Find existing value expression that is the same as T,
+ and return it if it exists. */
+
+static inline tree
+find_existing_value_expr (tree t, tree stmt)
+{
+ bitmap_iterator bi;
+ unsigned int bii;
+ tree vh;
+ bitmap_set_t exprset;
+
+ if (REFERENCE_CLASS_P (t) || TREE_CODE (t) == CALL_EXPR || DECL_P (t))
+ vh = vn_lookup_with_stmt (t, stmt);
+ else
+ vh = vn_lookup (t);
+
+ if (!vh)
+ return NULL;
+ exprset = VALUE_HANDLE_EXPR_SET (vh);
+ FOR_EACH_EXPR_ID_IN_SET (exprset, bii, bi)
+ {
+ tree efi = expression_for_id (bii);
+ if (expressions_equal_p (t, efi))
+ return efi;
+ }
+ return NULL;
+}
/* Given a unary or binary expression EXPR, create and return a new
expression with the same structure as EXPR but with its operands
int i;
enum tree_code code = TREE_CODE (expr);
tree vexpr;
- alloc_pool pool;
+ alloc_pool pool = NULL;
+ tree efi;
gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
|| TREE_CODE_CLASS (code) == tcc_binary
|| TREE_CODE_CLASS (code) == tcc_comparison
|| TREE_CODE_CLASS (code) == tcc_reference
|| TREE_CODE_CLASS (code) == tcc_expression
+ || TREE_CODE_CLASS (code) == tcc_vl_exp
|| TREE_CODE_CLASS (code) == tcc_exceptional
|| TREE_CODE_CLASS (code) == tcc_declaration);
pool = binary_node_pool;
else if (TREE_CODE_CLASS (code) == tcc_comparison)
pool = comparison_node_pool;
- else if (TREE_CODE_CLASS (code) == tcc_exceptional)
- {
- gcc_assert (code == TREE_LIST);
- pool = list_node_pool;
- }
else
- {
- gcc_assert (code == CALL_EXPR);
- pool = expression_node_pool;
- }
-
- vexpr = (tree) pool_alloc (pool);
- memcpy (vexpr, expr, tree_size (expr));
+ gcc_assert (code == CALL_EXPR);
- /* This case is only for TREE_LIST's that appear as part of
- CALL_EXPR's. Anything else is a bug, but we can't easily verify
- this, hence this comment. TREE_LIST is not handled by the
- general case below is because they don't have a fixed length, or
- operands, so you can't access purpose/value/chain through
- TREE_OPERAND macros. */
-
- if (code == TREE_LIST)
+ if (code == CALL_EXPR)
+ vexpr = temp_copy_call_expr (expr);
+ else
{
- tree op = NULL_TREE;
- tree temp = NULL_TREE;
- if (TREE_CHAIN (vexpr))
- temp = create_value_expr_from (TREE_CHAIN (vexpr), block, stmt);
- TREE_CHAIN (vexpr) = temp ? temp : TREE_CHAIN (vexpr);
-
-
- /* Recursively value-numberize reference ops. */
- if (REFERENCE_CLASS_P (TREE_VALUE (vexpr)))
- {
- tree tempop;
- op = TREE_VALUE (vexpr);
- tempop = create_value_expr_from (op, block, stmt);
- op = tempop ? tempop : op;
-
- TREE_VALUE (vexpr) = vn_lookup_or_add (op, stmt);
- }
- else
- {
- op = TREE_VALUE (vexpr);
- TREE_VALUE (vexpr) = vn_lookup_or_add (TREE_VALUE (vexpr), NULL);
- }
- /* This is the equivalent of inserting op into EXP_GEN like we
- do below */
- if (!is_undefined_value (op))
- value_insert_into_set (EXP_GEN (block), op);
-
- return vexpr;
+ vexpr = (tree) pool_alloc (pool);
+ memcpy (vexpr, expr, tree_size (expr));
}
- for (i = 0; i < TREE_CODE_LENGTH (code); i++)
+ for (i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
{
- tree val, op;
+ tree val = NULL_TREE;
+ tree op;
op = TREE_OPERAND (expr, i);
if (op == NULL_TREE)
{
tree tempop = create_value_expr_from (op, block, stmt);
op = tempop ? tempop : op;
- val = vn_lookup_or_add (op, stmt);
+ val = vn_lookup_or_add_with_stmt (op, stmt);
}
- else if (TREE_CODE (op) == TREE_LIST)
+ else
{
- tree tempop;
-
- gcc_assert (TREE_CODE (expr) == CALL_EXPR);
- tempop = create_value_expr_from (op, block, stmt);
-
- op = tempop ? tempop : op;
- vn_lookup_or_add (op, NULL);
- /* Unlike everywhere else, we do *not* want to replace the
- TREE_LIST itself with a value number, because support
- functions we call will blow up. */
- val = op;
+ val = vn_lookup_or_add (op);
}
- else
- /* Create a value handle for OP and add it to VEXPR. */
- val = vn_lookup_or_add (op, NULL);
-
- if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST)
- value_insert_into_set (EXP_GEN (block), op);
-
+ if (TREE_CODE (op) != TREE_LIST)
+ add_to_exp_gen (block, op);
+
if (TREE_CODE (val) == VALUE_HANDLE)
TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
TREE_OPERAND (vexpr, i) = val;
}
-
+ efi = find_existing_value_expr (vexpr, stmt);
+ if (efi)
+ return efi;
+ get_or_alloc_expression_id (vexpr);
return vexpr;
}
-
-
-/* Insert extra phis to merge values that are fully available from
- preds of BLOCK, but have no dominating representative coming from
- block DOM. */
-
-static void
-insert_extra_phis (basic_block block, basic_block dom)
-{
-
- if (!single_pred_p (block))
- {
- edge e;
- edge_iterator ei;
- bool first = true;
- bitmap_set_t tempset = bitmap_set_new ();
-
- FOR_EACH_EDGE (e, ei, block->preds)
- {
- /* We cannot handle abnormal incoming edges correctly. */
- if (e->flags & EDGE_ABNORMAL)
- return;
-
- if (first)
- {
- bitmap_set_copy (tempset, AVAIL_OUT (e->src));
- first = false;
- }
- else
- bitmap_set_and (tempset, AVAIL_OUT (e->src));
- }
-
- if (dom)
- bitmap_set_and_compl (tempset, AVAIL_OUT (dom));
-
- if (!bitmap_set_empty_p (tempset))
- {
- unsigned int i;
- bitmap_iterator bi;
-
- EXECUTE_IF_SET_IN_BITMAP (tempset->expressions, 0, i, bi)
- {
- tree name = ssa_name (i);
- tree val = get_value_handle (name);
- tree temp;
-
- if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
- continue;
-
- 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))
- {
- fprintf (dump_file, "Creating phi ");
- print_generic_expr (dump_file, temp, 0);
- fprintf (dump_file, " to merge available but not dominating values ");
- }
-
- add_referenced_var (temp);
- temp = create_phi_node (temp, block);
- NECESSARY (temp) = 0;
- VEC_safe_push (tree, heap, inserted_exprs, temp);
-
- FOR_EACH_EDGE (e, ei, block->preds)
- {
- tree leader = bitmap_find_leader (AVAIL_OUT (e->src), val);
-
- gcc_assert (leader);
- add_phi_arg (temp, leader, e);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- print_generic_expr (dump_file, leader, 0);
- fprintf (dump_file, " in block %d,", e->src->index);
- }
- }
-
- vn_add (PHI_RESULT (temp), val);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\n");
- }
- }
- }
-}
-
-/* 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) != MODIFY_EXPR
- || !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 (TREE_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 = TREE_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))
- 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. */
{
case INDIRECT_REF:
{
- tree temp = pool_alloc (reference_node_pool);
+ tree temp = (tree) 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:
+ case GIMPLE_MODIFY_STMT:
{
- tree temp = pool_alloc (modify_expr_node_pool);
+ tree temp = (tree) 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));
+ GIMPLE_STMT_OPERAND (temp, 0) =
+ poolify_tree (GIMPLE_STMT_OPERAND (temp, 0));
+ GIMPLE_STMT_OPERAND (temp, 1) =
+ poolify_tree (GIMPLE_STMT_OPERAND (temp, 1));
return temp;
}
break;
static tree modify_expr_template;
-/* Allocate a MODIFY_EXPR with TYPE, and operands OP1, OP2 in the
+/* Allocate a GIMPLE_MODIFY_STMT with TYPE, and operands OP1, OP2 in the
alloc pools and return it. */
static tree
-poolify_modify_expr (tree type, tree op1, tree op2)
+poolify_modify_stmt (tree op1, tree op2)
{
if (modify_expr_template == NULL)
- modify_expr_template = build2 (MODIFY_EXPR, type, op1, op2);
+ modify_expr_template = build_gimple_modify_stmt (op1, op2);
- TREE_OPERAND (modify_expr_template, 0) = op1;
- TREE_OPERAND (modify_expr_template, 1) = op2;
- TREE_TYPE (modify_expr_template) = type;
+ GIMPLE_STMT_OPERAND (modify_expr_template, 0) = op1;
+ GIMPLE_STMT_OPERAND (modify_expr_template, 1) = op2;
return poolify_tree (modify_expr_template);
}
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)
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == INDIRECT_REF
+ && !AGGREGATE_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 0)))
+ && TREE_CODE (TREE_TYPE (GIMPLE_STMT_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;
+ tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ tree new_tree;
bool notokay = false;
FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
{
storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
+ if (TREE_CODE (TREE_TYPE (storetemp)) == VECTOR_TYPE)
+ DECL_GIMPLE_REG_P (storetemp) = 1;
get_var_ann (storetemp);
}
- new = poolify_modify_expr (TREE_TYPE (stmt), storetemp, lhs);
+ new_tree = poolify_modify_stmt (storetemp, lhs);
- lhs = make_ssa_name (storetemp, new);
- TREE_OPERAND (new, 0) = lhs;
- create_ssa_artficial_load_stmt (new, stmt);
+ lhs = make_ssa_name (storetemp, new_tree);
+ GIMPLE_STMT_OPERAND (new_tree, 0) = lhs;
+ create_ssa_artificial_load_stmt (new_tree, 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);
+ NECESSARY (new_tree) = 0;
+ VEC_safe_push (tree, heap, inserted_exprs, new_tree);
+ VEC_safe_push (tree, heap, need_creation, new_tree);
+ bsi_insert_after (&bsi, new_tree, BSI_NEW_STMT);
}
}
}
if (NECESSARY (stmt))
{
block_stmt_iterator bsi;
- tree newstmt;
+ tree newstmt, tmp;
/* Mark the temp variable as referenced */
- add_referenced_var (SSA_NAME_VAR (TREE_OPERAND (stmt, 0)));
+ add_referenced_var (SSA_NAME_VAR (GIMPLE_STMT_OPERAND (stmt, 0)));
/* Put the new statement in GC memory, fix up the
SSA_NAME_DEF_STMT on it, and then put it in place of
as a plain ssa name copy. */
bsi = bsi_for_stmt (stmt);
bsi_prev (&bsi);
- newstmt = build2 (MODIFY_EXPR, void_type_node,
- TREE_OPERAND (stmt, 0),
- TREE_OPERAND (bsi_stmt (bsi), 1));
- SSA_NAME_DEF_STMT (TREE_OPERAND (newstmt, 0)) = newstmt;
+ tmp = GIMPLE_STMT_OPERAND (bsi_stmt (bsi), 1);
+ newstmt = build_gimple_modify_stmt (GIMPLE_STMT_OPERAND (stmt, 0),
+ tmp);
+ SSA_NAME_DEF_STMT (GIMPLE_STMT_OPERAND (newstmt, 0)) = newstmt;
bsi_insert_before (&bsi, newstmt, BSI_SAME_STMT);
bsi = bsi_for_stmt (stmt);
bsi_remove (&bsi, true);
}
}
-/* 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;
+ 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;
- if (!((TREE_CODE (expr) == NOP_EXPR
- || TREE_CODE (expr) == CONVERT_EXPR)
- && TREE_CODE (TREE_OPERAND (expr, 0)) == VALUE_HANDLE
- && !VALUE_HANDLE_VUSES (TREE_OPERAND (expr, 0))))
- return false;
+ /* 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)
+ {
+ tree defstmt = SSA_NAME_DEF_STMT (val);
+
+ gcc_assert (VN_INFO (val)->valnum == val);
+ /* PHI nodes can't have vuses and attempts to iterate over
+ their VUSE operands will crash. */
+ if (TREE_CODE (defstmt) == PHI_NODE || IS_EMPTY_STMT (defstmt))
+ defstmt = NULL;
+ {
+ tree defstmt2 = SSA_NAME_DEF_STMT (name);
+ if (TREE_CODE (defstmt2) != PHI_NODE &&
+ !ZERO_SSA_OPERANDS (defstmt2, SSA_OP_ALL_VIRTUALS))
+ gcc_assert (defstmt);
+ }
+ valvh = vn_lookup_or_add_with_stmt (val, defstmt);
+ }
+
+ 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 (valvh)
+ return valvh;
+ else
+ return val;
+ }
+ return NULL_TREE;
+}
- t = fold_unary (TREE_CODE (expr), TREE_TYPE (expr),
- VALUE_HANDLE_EXPR_SET (TREE_OPERAND (expr, 0))->head->expr);
- if (!t)
- return false;
+/* Create value handles for PHI in BLOCK. */
- /* Strip useless type conversions, which is safe in the optimizers but
- not generally in fold. */
- STRIP_USELESS_TYPE_CONVERSION (t);
+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));
+ }
+}
- /* 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);
+/* Return true if both the statement and the value handles have no
+ vuses, or both the statement and the value handle do have vuses.
+
+ Unlike SCCVN, PRE needs not only to know equivalence, but what the
+ actual vuses are so it can translate them through blocks. Thus,
+ we have to make a new value handle if the existing one has no
+ vuses but needs them. */
+
+static bool
+vuse_equiv (tree vh1, tree stmt)
+{
+ bool stmt_has_vuses = !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES);
+ return (VALUE_HANDLE_VUSES (vh1) && stmt_has_vuses)
+ || (!VALUE_HANDLE_VUSES (vh1) && !stmt_has_vuses);
+}
+
+/* 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)
+ {
+ 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;
- if (t && t != expr)
+ }
+ 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 if necessary and
+ call it a day */
+ if (get_value_handle (lhs) == NULL)
+ vn_lookup_or_add (lhs);
+ 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)
+ && (!lhsval || !is_gimple_min_invariant (lhsval)))
+ {
+ /* 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 && vuse_equiv (lhsval, stmt))
+ {
+ set_value_handle (newt, lhsval);
+ if (!is_gimple_min_invariant (lhsval))
+ add_to_value (lhsval, newt);
+ }
+ else
+ {
+ tree val = vn_lookup_or_add_with_stmt (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))
{
- *expr_p = t;
+
+ 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.
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);
param;
param = TREE_CHAIN (param))
{
- if (default_def (param) != NULL)
+ if (gimple_default_def (cfun, param) != NULL)
{
- tree def = default_def (param);
- vn_lookup_or_add (def, NULL);
- bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
+ tree def = gimple_default_def (cfun, param);
+
+ vn_lookup_or_add (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);
}
}
if (cfun->static_chain_decl)
{
param = cfun->static_chain_decl;
- if (default_def (param) != NULL)
- {
- tree def = default_def (param);
- vn_lookup_or_add (def, NULL);
- bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
- bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
- }
+ if (gimple_default_def (cfun, param) != NULL)
+ {
+ tree def = gimple_default_def (cfun, param);
+
+ vn_lookup_or_add (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);
+ }
}
/* Allocate the worklist. */
if (dom)
bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
- if (!in_fre)
- insert_extra_phis (block, dom);
-
/* 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. */
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
- && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
+ if (TREE_CODE (stmt) == RETURN_EXPR
+ && !ann->has_volatile_ops)
{
- tree lhs = TREE_OPERAND (stmt, 0);
- tree rhs = TREE_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))
- continue;
+ tree realstmt = stmt;
+ tree lhs;
+ tree rhs;
- STRIP_USELESS_TYPE_CONVERSION (rhs);
- if (can_value_number_operation (rhs))
+ stmt = TREE_OPERAND (stmt, 0);
+ if (stmt && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
{
- /* 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)
+ 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 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
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- tree val = vn_lookup_or_add (newt, stmt);
- vn_add (lhs, val);
- value_insert_into_set (EXP_GEN (block), newt);
+ 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);
}
- bitmap_insert_into_set (TMP_GEN (block), lhs);
- bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
+ vn_add (lhs, VN_INFO (lhs)->valnum);
continue;
}
+
+ if (TREE_CODE (rhs) == SSA_NAME)
+ 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),
+ AVAIL_OUT (block));
}
- 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))
- value_insert_into_set (EXP_GEN (block), rhs);
- continue;
- }
+ continue;
+ }
+
+ else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ && !ann->has_volatile_ops
+ && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
+ && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
+ (GIMPLE_STMT_OPERAND (stmt, 0)))
+ {
+ if (make_values_for_stmt (stmt, block))
+ continue;
+
}
/* For any other statement that we don't recognize, simply
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 (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
block_stmt_iterator i;
for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
- {
- tree stmt = bsi_stmt (i);
+ {
+ tree stmt = bsi_stmt (i);
/* Lookup the RHS of the expression, see if we have an
available computation for it. If so, replace the RHS with
the available computation. */
- if (TREE_CODE (stmt) == MODIFY_EXPR
- && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
- && TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
- && !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
+ && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) != SSA_NAME
+ && !is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt, 1))
&& !stmt_ann (stmt)->has_volatile_ops)
{
- tree lhs = TREE_OPERAND (stmt, 0);
- tree *rhs_p = &TREE_OPERAND (stmt, 1);
+ tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ tree *rhs_p = &GIMPLE_STMT_OPERAND (stmt, 1);
tree sprime;
sprime = bitmap_find_leader (AVAIL_OUT (b),
- vn_lookup (lhs, NULL));
+ get_value_handle (lhs));
+
if (sprime
&& sprime != lhs
&& (TREE_CODE (*rhs_p) != SSA_NAME
which may require adding a simple cast, which fold_convert
will do for us. */
if (TREE_CODE (*rhs_p) != SSA_NAME
- && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p),
- TREE_TYPE (sprime)))
+ && !useless_type_conversion_p (TREE_TYPE (*rhs_p),
+ TREE_TYPE (sprime)))
sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
pre_stats.eliminations++;
}
}
}
- }
+ }
}
}
VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
for (k = 0; k < PHI_NUM_ARGS (t); k++)
- {
+ {
tree arg = PHI_ARG_DEF (t, k);
if (TREE_CODE (arg) == SSA_NAME)
{
else
{
/* Propagate through the operands. Examine all the USE, VUSE and
- V_MAY_DEF 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 V_MAY_DEF expressions are also needed as they
+ /* The operands of VDEF expressions are also needed as they
represent potential definitions that may reach this
- statement (V_MAY_DEF 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)
if (TREE_CODE (t) == PHI_NODE)
{
- remove_phi_node (t, NULL);
+ remove_phi_node (t, NULL, true);
}
else
{
init_pre (bool do_fre)
{
basic_block bb;
-
+
+ next_expression_id = 0;
+ expressions = NULL;
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 (LOOPS_NORMAL);
+ loop_optimizer_init (LOOPS_NORMAL);
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
- /* If block 0 has more than one predecessor, it means that its PHI
- nodes will have arguments coming from block -1. This creates
- problems for several places in PRE that keep local arrays indexed
- by block number. To prevent this, we split the edge coming from
- ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
- different than -1 we wouldn't have to hack this. tree-ssa-dce.c
- needs a similar change). */
- if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR)))
- if (!(single_succ_edge (ENTRY_BLOCK_PTR)->flags & EDGE_ABNORMAL))
- split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
+
+ postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
+ post_order_compute (postorder, false, false);
FOR_ALL_BB (bb)
- bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
+ bb->aux = xcalloc (1, sizeof (struct bb_bitmap_sets));
+
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+ calculate_dominance_info (CDI_DOMINATORS);
bitmap_obstack_initialize (&grand_bitmap_obstack);
- phi_translate_table = htab_create (511, expr_pred_trans_hash,
+ phi_translate_table = htab_create (5110, expr_pred_trans_hash,
expr_pred_trans_eq, free);
- value_set_pool = create_alloc_pool ("Value sets",
- sizeof (struct value_set), 30);
+ seen_during_translate = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_set_pool = create_alloc_pool ("Bitmap sets",
sizeof (struct bitmap_set), 30);
- value_set_node_pool = create_alloc_pool ("Value set nodes",
- sizeof (struct value_set_node), 30);
- calculate_dominance_info (CDI_POST_DOMINATORS);
- calculate_dominance_info (CDI_DOMINATORS);
binary_node_pool = create_alloc_pool ("Binary tree nodes",
- tree_code_size (PLUS_EXPR), 30);
+ tree_code_size (PLUS_EXPR), 30);
unary_node_pool = create_alloc_pool ("Unary tree nodes",
tree_code_size (NEGATE_EXPR), 30);
reference_node_pool = create_alloc_pool ("Reference tree nodes",
tree_code_size (ARRAY_REF), 30);
- expression_node_pool = create_alloc_pool ("Expression tree nodes",
- tree_code_size (CALL_EXPR), 30);
- list_node_pool = create_alloc_pool ("List tree nodes",
- 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),
+ tree_code_size (EQ_EXPR), 30);
+ modify_expr_node_pool = create_alloc_pool ("GIMPLE_MODIFY_STMT nodes",
+ tree_code_size (GIMPLE_MODIFY_STMT),
30);
+ obstack_init (&temp_call_expr_obstack);
modify_expr_template = NULL;
FOR_ALL_BB (bb)
{
- EXP_GEN (bb) = set_new (true);
+ EXP_GEN (bb) = bitmap_set_new ();
PHI_GEN (bb) = bitmap_set_new ();
TMP_GEN (bb) = bitmap_set_new ();
AVAIL_OUT (bb) = bitmap_set_new ();
}
+ maximal_set = in_fre ? NULL : bitmap_set_new ();
need_eh_cleanup = BITMAP_ALLOC (NULL);
}
/* Deallocate data structures used by PRE. */
static void
-fini_pre (bool do_fre)
+fini_pre (void)
{
basic_block bb;
unsigned int i;
+ free (postorder);
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);
- free_alloc_pool (value_set_node_pool);
free_alloc_pool (binary_node_pool);
free_alloc_pool (reference_node_pool);
free_alloc_pool (unary_node_pool);
- 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);
}
free_dominance_info (CDI_POST_DOMINATORS);
- vn_delete ();
if (!bitmap_empty_p (need_eh_cleanup))
{
&& TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
SSA_NAME_VALUE (name) = NULL;
}
- if (!do_fre && current_loops)
- {
- loop_optimizer_finalize (current_loops);
- current_loops = NULL;
- }
+ if (current_loops != NULL)
+ loop_optimizer_finalize ();
}
/* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
static void
execute_pre (bool do_fre)
{
+
+ do_partial_partial = optimize > 2;
init_pre (do_fre);
if (!do_fre)
insert_fake_stores ();
/* Collect and value number expressions computed in each basic block. */
+ run_scc_vn ();
+ switch_to_PRE_table ();
compute_avail ();
if (dump_file && (dump_flags & TDF_DETAILS))
FOR_ALL_BB (bb)
{
- print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
- bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen",
+ print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
+ print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen",
bb->index);
- bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
+ print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out",
bb->index);
}
}
computing ANTIC, either, even though it's plenty fast. */
if (!do_fre && n_basic_blocks < 4000)
{
- vuse_names = XCNEWVEC (bitmap, num_ssa_names);
- compute_rvuse_and_antic_safe ();
compute_antic ();
insert ();
- free (vuse_names);
}
/* Remove all the redundant expressions. */
eliminate ();
-
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
+ fprintf (dump_file, "PA inserted: %d\n", pre_stats.pa_insert);
fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
}
-
bsi_commit_edge_inserts ();
+ free_scc_vn ();
+ clear_expression_ids ();
if (!do_fre)
{
remove_dead_inserted_code ();
realify_fake_stores ();
}
- fini_pre (do_fre);
-
+ fini_pre ();
}
/* Gate and execute functions for PRE. */
OSDN Git Service
