/* SSA-PRE for trees.
- Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
<stevenb@suse.de>
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
#include "tree.h"
#include "basic-block.h"
#include "alloc-pool.h"
#include "tree-pass.h"
#include "flags.h"
-#include "splay-tree.h"
#include "bitmap.h"
#include "langhooks.h"
+#include "cfgloop.h"
/* TODO:
1. Avail sets can be shared by making an avail_find_leader that
walks up the dominator tree and looks in those avail sets.
This might affect code optimality, it's unclear right now.
- 2. Load motion can be performed by value numbering the loads the
- same as we do other expressions. This requires iterative
- hashing the vuses into the values. Right now we simply assign
- a new value every time we see a statement with a vuse.
- 3. Strength reduction can be performed by anticipating expressions
+ 2. Strength reduction can be performed by anticipating expressions
we can repair later on.
- 4. Our canonicalization of expressions during lookups don't take
- constants into account very well. In particular, we don't fold
- anywhere, so we can get situations where we stupidly think
- something is a new value (a + 1 + 1 vs a + 2). This is somewhat
- expensive to fix, but it does expose a lot more eliminations.
- It may or not be worth it, depending on how critical you
- consider PRE vs just plain GRE.
+ 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
useful only for debugging, since we don't do identity lookups. */
+static bool in_fre = false;
+
/* A value set element. Basically a single linked list of
expressions/values. */
typedef struct value_set_node
/* An unordered bitmap set. One bitmap tracks values, the other,
- expressions. */
+ expressions. */
typedef struct bitmap_set
{
bitmap expressions;
a given basic block. */
bitmap_set_t avail_out;
- /* The ANTIC_IN set, which represents which values are anticiptable
+ /* The ANTIC_IN set, which represents which values are anticipatable
in a given basic block. */
value_set_t antic_in;
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;
} *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 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
/* This structure is used to keep track of statistics on what
optimization PRE was able to perform. */
/* The number of new PHI nodes added by PRE. */
int phis;
+
+ /* The number of values found constant. */
+ int constified;
+
} pre_stats;
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
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;
+
+/* 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. */
typedef struct expr_pred_trans_d
{
- /* The expression. */
+ /* The expression. */
tree e;
/* The predecessor block along which we translated the expression. */
basic_block pred;
+ /* vuses associated with the expression. */
+ VEC (tree, gc) *vuses;
+
/* The value that resulted from the translation. */
tree v;
+
/* The hashcode for the expression, pred pair. This is cached for
speed reasons. */
hashval_t hashcode;
const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
basic_block b1 = ve1->pred;
basic_block b2 = ve2->pred;
-
+ int i;
+ tree vuse1;
/* If they are not translations for the same basic block, they can't
be equal. */
if (b1 != b2)
return false;
+
/* If they are for the same basic block, determine if the
- expressions are equal. */
- if (expressions_equal_p (ve1->e, ve2->e))
+ expressions are equal. */
+ if (!expressions_equal_p (ve1->e, ve2->e))
+ return false;
+
+ /* Make sure the vuses are equivalent. */
+ if (ve1->vuses == ve2->vuses)
return true;
- return false;
+ if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
+ return false;
+
+ for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
+ {
+ if (VEC_index (tree, ve2->vuses, i) != vuse1)
+ return false;
+ }
+
+ return true;
}
/* Search in the phi translation table for the translation of
- expression E in basic block PRED. Return the translated value, if
- found, NULL otherwise. */
+ expression E in basic block PRED with vuses VUSES.
+ Return the translated value, if found, NULL otherwise. */
static inline tree
-phi_trans_lookup (tree e, basic_block pred)
+phi_trans_lookup (tree e, basic_block pred, VEC (tree, gc) *vuses)
{
void **slot;
struct expr_pred_trans_d ept;
+
ept.e = e;
ept.pred = pred;
- ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
+ ept.vuses = vuses;
+ ept.hashcode = vn_compute (e, (unsigned long) pred);
slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
NO_INSERT);
if (!slot)
}
-/* Add the tuple mapping from {expression E, basic block PRED} to
+/* Add the tuple mapping from {expression E, basic block PRED, vuses VUSES} to
value V, to the phi translation table. */
static inline void
-phi_trans_add (tree e, tree v, basic_block pred)
+phi_trans_add (tree e, tree v, basic_block pred, VEC (tree, gc) *vuses)
{
void **slot;
- expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
+ expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
new_pair->e = e;
new_pair->pred = pred;
+ new_pair->vuses = vuses;
new_pair->v = v;
- new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
+ new_pair->hashcode = vn_compute (e, (unsigned long) pred);
slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
new_pair->hashcode, INSERT);
if (*slot)
static void
value_remove_from_set_bitmap (value_set_t set, tree v)
{
-#ifdef ENABLE_CHECKING
- if (!set->indexed)
- abort ();
-#endif
+ gcc_assert (set->indexed);
if (!set->values)
return;
static inline void
value_insert_into_set_bitmap (value_set_t set, tree v)
{
-#ifdef ENABLE_CHECKING
- if (!set->indexed)
- abort ();
-#endif
+ gcc_assert (set->indexed);
if (set->values == NULL)
- {
- set->values = BITMAP_GGC_ALLOC ();
- bitmap_clear (set->values);
- }
+ set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
}
static bitmap_set_t
bitmap_set_new (void)
{
- bitmap_set_t ret = pool_alloc (bitmap_set_pool);
- ret->expressions = BITMAP_GGC_ALLOC ();
- ret->values = BITMAP_GGC_ALLOC ();
- bitmap_clear (ret->expressions);
- bitmap_clear (ret->values);
+ bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
+ ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
+ ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
return ret;
}
set_new (bool indexed)
{
value_set_t ret;
- ret = pool_alloc (value_set_pool);
+ ret = (value_set_t) pool_alloc (value_set_pool);
ret->head = ret->tail = NULL;
ret->length = 0;
ret->indexed = indexed;
{
tree val;
/* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
- if (TREE_CODE (expr) != SSA_NAME)
- abort ();
+ gcc_assert (TREE_CODE (expr) == SSA_NAME);
val = get_value_handle (expr);
- if (val == NULL)
- abort ();
+ 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));
+ bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
+ }
}
/* Insert EXPR into SET. */
static void
insert_into_set (value_set_t set, tree expr)
{
- value_set_node_t newnode = pool_alloc (value_set_node_pool);
+ 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 (val == NULL)
- abort ();
+ 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
bitmap_copy (dest->values, orig->values);
}
+/* Perform bitmapped set operation DEST &= ORIG. */
+
+static void
+bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
+{
+ 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);
+ }
+
+}
+
+/* Perform bitmapped value set operation DEST = DEST & ~ORIG. */
+
+static void
+bitmap_set_and_compl (bitmap_set_t dest, bitmap_set_t orig)
+{
+ bitmap_iterator bi;
+ unsigned int i;
+ bitmap temp = BITMAP_ALLOC (&grand_bitmap_obstack);
+
+ bitmap_and_compl_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);
+ }
+}
+
+/* Return true if the bitmap set SET is empty. */
+
+static bool
+bitmap_set_empty_p (bitmap_set_t set)
+{
+ return bitmap_empty_p (set->values);
+}
+
/* Copy the set ORIG to the set DEST. */
static void
if (is_gimple_min_invariant (val))
return true;
- if (set->length == 0)
+ if (!set || set->length == 0)
return false;
return value_exists_in_set_bitmap (set, val);
static bool
bitmap_set_contains (bitmap_set_t set, tree expr)
{
+ /* All constants are in every set. */
+ if (is_gimple_min_invariant (get_value_handle (expr)))
+ return true;
+
/* XXX: Bitmapped sets only contain SSA_NAME's for now. */
if (TREE_CODE (expr) != SSA_NAME)
return false;
return;
if (!bitmap_set_contains_value (set, lookfor))
return;
+
/* The number of expressions having a given value is usually
significantly less than the total number of expressions in SET.
Thus, rather than check, for each expression in SET, whether it
return ret;
}
-/* Return true if two sets are equal. */
+/* Return true if two sets are equal. */
static bool
set_equal (value_set_t a, value_set_t b)
return true;
}
-/* Replace an instance of EXPR's VALUE with EXPR in SET. */
+/* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
+ and add it otherwise. */
static void
bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
{
tree val = get_value_handle (expr);
- bitmap_set_replace_value (set, val, expr);
+ if (bitmap_set_contains_value (set, val))
+ bitmap_set_replace_value (set, val, expr);
+ else
+ bitmap_insert_into_set (set, expr);
}
/* Insert EXPR into SET if EXPR's value is not already present in
bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
{
tree val = get_value_handle (expr);
+
if (is_gimple_min_invariant (val))
return;
fprintf (outfile, "%s[%d] := { ", setname, blockindex);
if (set)
{
- int i;
- EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i,
- {
- print_generic_expr (outfile, ssa_name (i), 0);
+ bool first = true;
+ unsigned i;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
+ {
+ if (!first)
+ fprintf (outfile, ", ");
+ first = false;
+ print_generic_expr (outfile, ssa_name (i), 0);
- fprintf (outfile, " (");
- print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
- fprintf (outfile, ") ");
- if (bitmap_last_set_bit (set->expressions) != i)
- fprintf (outfile, ", ");
- });
+ fprintf (outfile, " (");
+ print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
+ fprintf (outfile, ") ");
+ }
}
fprintf (outfile, " }\n");
}
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. */
+
+static tree
+fully_constant_expression (tree t)
+{
+ tree folded;
+ folded = fold (t);
+ if (folded && is_gimple_min_invariant (folded))
+ return folded;
+ 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*/
+
+static tree
+pool_copy_list (tree list)
+{
+ 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;
+}
+
+/* Translate the vuses in the VUSES vector backwards through phi
+ nodes, so that they have the value they would have in BLOCK. */
+
+static VEC(tree, gc) *
+translate_vuses_through_block (VEC (tree, gc) *vuses, basic_block block)
+{
+ tree oldvuse;
+ VEC(tree, gc) *result = NULL;
+ int i;
+
+ for (i = 0; VEC_iterate (tree, vuses, i, oldvuse); i++)
+ {
+ tree phi = SSA_NAME_DEF_STMT (oldvuse);
+ if (TREE_CODE (phi) == PHI_NODE)
+ {
+ edge e = find_edge (block, bb_for_stmt (phi));
+ if (e)
+ {
+ tree def = PHI_ARG_DEF (phi, e->dest_idx);
+ if (def != oldvuse)
+ {
+ if (!result)
+ result = VEC_copy (tree, gc, vuses);
+ VEC_replace (tree, result, i, def);
+ }
+ }
+ }
+ }
+ if (result)
+ {
+ sort_vuses (result);
+ return result;
+ }
+ return vuses;
+
+}
/* Translate EXPR using phis in PHIBLOCK, so that it has the values of
the phis in PRED. Return NULL if we can't find a leader for each
part of the translated expression. */
{
tree phitrans = NULL;
tree oldexpr = expr;
-
if (expr == NULL)
return NULL;
- /* Phi translations of a given expression don't change, */
- phitrans = phi_trans_lookup (expr, pred);
+ if (is_gimple_min_invariant (expr))
+ return expr;
+
+ /* Phi translations of a given expression don't change. */
+ if (EXPR_P (expr))
+ {
+ tree vh;
+
+ vh = get_value_handle (expr);
+ if (vh && TREE_CODE (vh) == VALUE_HANDLE)
+ phitrans = phi_trans_lookup (expr, pred, VALUE_HANDLE_VUSES (vh));
+ else
+ phitrans = phi_trans_lookup (expr, pred, NULL);
+ }
+ else
+ phitrans = phi_trans_lookup (expr, pred, NULL);
+
if (phitrans)
return phitrans;
-
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
- case '2':
+ case tcc_expression:
+ {
+ 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 vh = get_value_handle (expr);
+ bool listchanged = false;
+ VEC (tree, gc) *vuses = VALUE_HANDLE_VUSES (vh);
+ VEC (tree, gc) *tvuses;
+
+ /* Call expressions are kind of weird because they have an
+ argument list. We don't want to value number the list
+ 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)
+ return NULL;
+ if (oldop2)
+ {
+ newop2 = phi_translate (find_leader (set, oldop2),
+ set, pred, phiblock);
+ if (newop2 == NULL)
+ return NULL;
+ }
+
+ /* 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))
+ {
+
+ tree oldval = TREE_VALUE (oldwalker);
+ tree newval;
+ if (oldval)
+ {
+ /* This may seem like a weird place for this
+ check, but it's actually the easiest place to
+ do it. We can't do it lower on in the
+ recursion because it's valid for pieces of a
+ component ref to be of AGGREGATE_TYPE, as long
+ as the outermost one is not.
+ To avoid *that* case, we have a check for
+ AGGREGATE_TYPE_P in insert_aux. However, that
+ check will *not* catch this case because here
+ 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);
+ if (newval == NULL)
+ return NULL;
+ if (newval != oldval)
+ {
+ listchanged = true;
+ TREE_VALUE (newwalker) = get_value_handle (newval);
+ }
+ }
+ }
+ if (listchanged)
+ vn_lookup_or_add (newarglist, NULL);
+
+ tvuses = translate_vuses_through_block (vuses, pred);
+
+ if (listchanged || (newop0 != oldop0) || (oldop2 != newop2)
+ || vuses != tvuses)
+ {
+ newexpr = (tree) pool_alloc (expression_node_pool);
+ memcpy (newexpr, expr, tree_size (expr));
+ 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);
+ vn_lookup_or_add_with_vuses (newexpr, tvuses);
+ expr = newexpr;
+ phi_trans_add (oldexpr, newexpr, pred, tvuses);
+ }
+ }
+ }
+ return expr;
+
+ case tcc_declaration:
+ {
+ VEC (tree, gc) * oldvuses = NULL;
+ VEC (tree, gc) * newvuses = NULL;
+
+ oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
+ if (oldvuses)
+ newvuses = translate_vuses_through_block (oldvuses, pred);
+
+ if (oldvuses != newvuses)
+ vn_lookup_or_add_with_vuses (expr, newvuses);
+
+ phi_trans_add (oldexpr, expr, pred, newvuses);
+ }
+ return expr;
+
+ case tcc_reference:
+ {
+ tree oldop0 = TREE_OPERAND (expr, 0);
+ tree oldop1 = NULL;
+ tree newop0;
+ tree newop1 = NULL;
+ tree oldop2 = NULL;
+ tree newop2 = NULL;
+ tree oldop3 = NULL;
+ tree newop3 = NULL;
+ tree newexpr;
+ VEC (tree, gc) * oldvuses = NULL;
+ VEC (tree, gc) * newvuses = NULL;
+
+ if (TREE_CODE (expr) != INDIRECT_REF
+ && TREE_CODE (expr) != COMPONENT_REF
+ && TREE_CODE (expr) != ARRAY_REF)
+ return NULL;
+
+ newop0 = phi_translate (find_leader (set, oldop0),
+ set, pred, phiblock);
+ 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);
+
+ if (newop1 == NULL)
+ return NULL;
+ oldop2 = TREE_OPERAND (expr, 2);
+ if (oldop2)
+ {
+ newop2 = phi_translate (find_leader (set, oldop2),
+ set, pred, phiblock);
+
+ if (newop2 == NULL)
+ return NULL;
+ }
+ oldop3 = TREE_OPERAND (expr, 3);
+ if (oldop3)
+ {
+ newop3 = phi_translate (find_leader (set, oldop3),
+ set, pred, phiblock);
+
+ if (newop3 == NULL)
+ return NULL;
+ }
+ }
+
+ oldvuses = VALUE_HANDLE_VUSES (get_value_handle (expr));
+ if (oldvuses)
+ newvuses = translate_vuses_through_block (oldvuses, pred);
+
+ if (newop0 != oldop0 || newvuses != oldvuses
+ || newop1 != oldop1
+ || newop2 != oldop2
+ || newop3 != oldop3)
+ {
+ tree t;
+
+ newexpr = 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)
+ {
+ TREE_OPERAND (newexpr, 1) = get_value_handle (newop1);
+ if (newop2)
+ TREE_OPERAND (newexpr, 2) = get_value_handle (newop2);
+ if (newop3)
+ TREE_OPERAND (newexpr, 3) = get_value_handle (newop3);
+ }
+
+ t = fully_constant_expression (newexpr);
+
+ if (t != newexpr)
+ {
+ pool_free (reference_node_pool, newexpr);
+ newexpr = t;
+ }
+ else
+ {
+ create_tree_ann (newexpr);
+ vn_lookup_or_add_with_vuses (newexpr, newvuses);
+ }
+ expr = newexpr;
+ phi_trans_add (oldexpr, newexpr, pred, newvuses);
+ }
+ }
+ return expr;
+ break;
+
+ case tcc_binary:
+ case tcc_comparison:
{
tree oldop1 = TREE_OPERAND (expr, 0);
tree oldop2 = TREE_OPERAND (expr, 1);
return NULL;
if (newop1 != oldop1 || newop2 != oldop2)
{
- newexpr = pool_alloc (binary_node_pool);
+ tree t;
+ newexpr = (tree) pool_alloc (binary_node_pool);
memcpy (newexpr, expr, tree_size (expr));
- create_tree_ann (newexpr);
TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
- vn_lookup_or_add (newexpr, NULL);
+ t = fully_constant_expression (newexpr);
+ if (t != newexpr)
+ {
+ pool_free (binary_node_pool, newexpr);
+ newexpr = t;
+ }
+ else
+ {
+ create_tree_ann (newexpr);
+ vn_lookup_or_add (newexpr, NULL);
+ }
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred);
+ phi_trans_add (oldexpr, newexpr, pred, NULL);
}
}
- break;
- /* XXX: Until we have PRE of loads working, none will be ANTIC.
- */
- case 'r':
- return NULL;
- break;
- case '1':
+ return expr;
+
+ case tcc_unary:
{
tree oldop1 = TREE_OPERAND (expr, 0);
tree newop1;
return NULL;
if (newop1 != oldop1)
{
- newexpr = pool_alloc (unary_node_pool);
+ tree t;
+ newexpr = (tree) pool_alloc (unary_node_pool);
memcpy (newexpr, expr, tree_size (expr));
- create_tree_ann (newexpr);
TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
- vn_lookup_or_add (newexpr, NULL);
+ t = fully_constant_expression (newexpr);
+ if (t != newexpr)
+ {
+ pool_free (unary_node_pool, newexpr);
+ newexpr = t;
+ }
+ else
+ {
+ create_tree_ann (newexpr);
+ vn_lookup_or_add (newexpr, NULL);
+ }
expr = newexpr;
- phi_trans_add (oldexpr, newexpr, pred);
+ phi_trans_add (oldexpr, newexpr, pred, NULL);
}
}
- break;
- case 'd':
- abort ();
- case 'x':
+ return expr;
+
+ case tcc_exceptional:
{
tree phi = NULL;
- int i;
- if (TREE_CODE (expr) != SSA_NAME)
- abort ();
+ edge e;
+ gcc_assert (TREE_CODE (expr) == SSA_NAME);
if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
phi = SSA_NAME_DEF_STMT (expr);
else
return expr;
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
- if (PHI_ARG_EDGE (phi, i)->src == pred)
- {
- tree val;
- if (is_undefined_value (PHI_ARG_DEF (phi, i)))
- return NULL;
- val = vn_lookup_or_add (PHI_ARG_DEF (phi, i), NULL);
- return PHI_ARG_DEF (phi, i);
- }
+ e = find_edge (pred, bb_for_stmt (phi));
+ if (e)
+ {
+ if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
+ return NULL;
+ vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
+ return PHI_ARG_DEF (phi, e->dest_idx);
+ }
}
- break;
+ return expr;
+
+ default:
+ gcc_unreachable ();
}
- 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. */
+
static void
phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
basic_block phiblock)
node = node->next)
{
tree translated;
- translated = phi_translate (node->expr, set, pred, phiblock);
- phi_trans_add (node->expr, translated, pred);
+ translated = phi_translate (node->expr, set, pred, phiblock);
+
+ /* Don't add constants or empty translations to the cache, since
+ we won't look them up that way, or use the result, anyway. */
+ if (translated && !is_gimple_min_invariant (translated))
+ {
+ tree vh = get_value_handle (translated);
+ VEC (tree, gc) *vuses;
+
+ /* The value handle itself may also be an invariant, in
+ which case, it has no vuses. */
+ vuses = !is_gimple_min_invariant (vh)
+ ? VALUE_HANDLE_VUSES (vh) : NULL;
+ phi_trans_add (node->expr, translated, pred, vuses);
+ }
+
if (translated != NULL)
value_insert_into_set (dest, translated);
}
return NULL;
}
+/* Given the vuse representative map, MAP, and an SSA version number,
+ ID, return the bitmap of names ID represents, or NULL, if none
+ exists. */
+
+static bitmap
+get_representative (bitmap *map, int id)
+{
+ if (map[id] != NULL)
+ return map[id];
+ return NULL;
+}
+
+/* A vuse is anticipable at the top of block x, from the bottom of the
+ block, if it reaches the top of the block, and is not killed in the
+ block. In effect, we are trying to see if the vuse is transparent
+ backwards in the block. */
+
+static bool
+vuses_dies_in_block_x (VEC (tree, gc) *vuses, basic_block block)
+{
+ int i;
+ tree vuse;
+
+ for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
+ {
+ /* Any places where this is too conservative, are places
+ where we created a new version and shouldn't have. */
+
+ if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse))
+ || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION (vuse)))
+ return true;
+ }
+ return false;
+}
+
/* Determine if the expression EXPR is valid in SET. This means that
we have a leader for each part of the expression (if it consists of
values), or the expression is an SSA_NAME.
- NB: We never should run into a case where we have SSA_NAME +
+ 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,
- the ANTIC sets, will only ever have SSA_NAME's or binary value
- expression (IE VALUE1 + VALUE2) */
+ the ANTIC sets, will only ever have SSA_NAME's or value expressions
+ (IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
static bool
-valid_in_set (value_set_t set, tree expr)
+valid_in_set (value_set_t set, tree expr, basic_block block)
{
- switch (TREE_CODE_CLASS (TREE_CODE (expr)))
+ tree vh = get_value_handle (expr);
+ switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
- case '2':
+ case tcc_binary:
+ case tcc_comparison:
{
tree op1 = TREE_OPERAND (expr, 0);
tree op2 = TREE_OPERAND (expr, 1);
return set_contains_value (set, op1) && set_contains_value (set, op2);
}
- break;
- case '1':
+
+ case tcc_unary:
{
tree op1 = TREE_OPERAND (expr, 0);
return set_contains_value (set, op1);
}
- break;
- /* XXX: Until PRE of loads works, no reference nodes are ANTIC.
- */
- case 'r':
+
+ case tcc_expression:
{
+ 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)))
+ return false;
+
+ /* Now check the operands. */
+ for (; arglist; arglist = TREE_CHAIN (arglist))
+ {
+ if (!set_contains_value (set, TREE_VALUE (arglist)))
+ return false;
+ }
+ return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
+ }
return false;
}
- case 'x':
+
+ case tcc_reference:
{
- if (TREE_CODE (expr) == SSA_NAME)
- return true;
- abort ();
+ if (TREE_CODE (expr) == INDIRECT_REF
+ || TREE_CODE (expr) == COMPONENT_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))
+ return false;
+ if (TREE_CODE (expr) == ARRAY_REF)
+ {
+ tree op1 = TREE_OPERAND (expr, 1);
+ 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))
+ return false;
+ gcc_assert (!op2 || is_gimple_min_invariant (op2)
+ || TREE_CODE (op2) == VALUE_HANDLE);
+ if (op2
+ && !set_contains_value (set, op2))
+ return false;
+ gcc_assert (!op3 || is_gimple_min_invariant (op3)
+ || TREE_CODE (op3) == VALUE_HANDLE);
+ if (op3
+ && !set_contains_value (set, op3))
+ return false;
+ }
+ return set_contains_value (ANTIC_SAFE_LOADS (block),
+ vh)
+ || !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
+ block);
+ }
}
- case 'c':
- abort ();
- }
- return false;
+ return false;
+
+ case tcc_exceptional:
+ gcc_assert (TREE_CODE (expr) == SSA_NAME);
+ return true;
+
+ case tcc_declaration:
+ return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh), block);
+
+ default:
+ /* No other cases should be encountered. */
+ gcc_unreachable ();
+ }
}
/* Clean the set of expressions that are no longer valid in SET. This
in SET. */
static void
-clean (value_set_t set)
+clean (value_set_t set, basic_block block)
{
value_set_node_t node;
value_set_node_t next;
while (node)
{
next = node->next;
- if (!valid_in_set (set, node->expr))
+ if (!valid_in_set (set, node->expr, block))
set_remove (set, node->expr);
node = next;
}
}
-/* Compute the ANTIC set for BLOCK.
-
-ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
-succs(BLOCK) > 1
-ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
-succs(BLOCK) == 1
+static sbitmap has_abnormal_preds;
-ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
-TMP_GEN[BLOCK])
+/* Compute the ANTIC set for BLOCK.
-Iterate until fixpointed.
+ If succs(BLOCK) > 1 then
+ ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
+ else if succs(BLOCK) == 1 then
+ ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(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. */
+ 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)
+compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
{
basic_block son;
- edge e;
bool changed = false;
value_set_t S, old, ANTIC_OUT;
value_set_node_t node;
-
+
ANTIC_OUT = S = NULL;
- /* If any edges from predecessors are abnormal, antic_in is empty, so
- punt. Remember that the block has an incoming abnormal edge by
- setting the BB_VISITED flag. */
- if (! (block->flags & BB_VISITED))
- {
- for (e = block->pred; e; e = e->pred_next)
- if (e->flags & EDGE_ABNORMAL)
- {
- block->flags |= BB_VISITED;
- break;
- }
- }
- if (block->flags & BB_VISITED)
- {
- S = NULL;
- goto visit_sons;
- }
-
+
+ /* 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);
- /* If the block has no successors, ANTIC_OUT is empty, because it is
- the exit block. */
- if (block->succ == NULL);
-
+ /* 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. */
- else if (block->succ->succ_next == NULL)
+ else if (single_succ_p (block))
{
- phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
- block, block->succ->dest);
+ phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)),
+ block, single_succ (block));
}
/* If we have multiple successors, we take the intersection of all of
them. */
else
{
- varray_type worklist;
+ VEC(basic_block, heap) * worklist;
edge e;
size_t i;
basic_block bprime, first;
+ edge_iterator ei;
- VARRAY_BB_INIT (worklist, 1, "succ");
- e = block->succ;
- while (e)
- {
- VARRAY_PUSH_BB (worklist, e->dest);
- e = e->succ_next;
- }
- first = VARRAY_BB (worklist, 0);
+ 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));
- for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
+ for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
{
- bprime = VARRAY_BB (worklist, i);
node = ANTIC_OUT->head;
while (node)
{
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;
}
}
- VARRAY_CLEAR (worklist);
+ VEC_free (basic_block, heap, worklist);
}
- /* Generate ANTIC_OUT - TMP_GEN */
+ /* Generate ANTIC_OUT - TMP_GEN. */
S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
/* Start ANTIC_IN with EXP_GEN - TMP_GEN */
ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block),
TMP_GEN (block),
true);
-
- /* 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);
- }
- clean (ANTIC_IN (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);
+
+ clean (ANTIC_IN (block), block);
if (!set_equal (old, ANTIC_IN (block)))
changed = true;
- visit_sons:
+ 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 (S)
print_value_set (dump_file, S, "S", 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);
+ changed |= compute_antic_aux (son,
+ TEST_BIT (has_abnormal_preds, son->index));
}
return changed;
}
compute_antic (void)
{
bool changed = true;
- basic_block bb;
int num_iterations = 0;
- FOR_ALL_BB (bb)
+ 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)
{
- ANTIC_IN (bb) = set_new (true);
- if (bb->flags & BB_VISITED)
- abort ();
+ 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);
+ changed = compute_antic_aux (EXIT_BLOCK_PTR, false);
}
- FOR_ALL_BB (bb)
- {
- bb->flags &= ~BB_VISITED;
- }
- if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
- fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
-}
+ sbitmap_free (has_abnormal_preds);
-/* Find a leader for an expression, or generate one using
- create_expression_by_pieces if it's ANTIC but
- complex.
- BLOCK is the basic_block we are looking for leaders in.
- EXPR is the expression to find a leader or generate for.
- STMTS is the statement list to put the inserted expressions on.
- Returns the SSA_NAME of the LHS of the generated expression or the
- leader. */
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
+}
-static tree
-find_or_generate_expression (basic_block block, tree expr, tree stmts)
+/* Print the names represented by the bitmap NAMES, to the file OUT. */
+static void
+dump_bitmap_of_names (FILE *out, bitmap names)
{
- tree genop;
- genop = bitmap_find_leader (AVAIL_OUT (block), expr);
- /* Depending on the order we process DOM branches in, the value
- may not have propagated to all the dom children yet during
- this iteration. In this case, the value will always be in
- the NEW_SETS for us already, having been propagated from our
- dominator. */
- if (genop == NULL)
- genop = bitmap_find_leader (NEW_SETS (block), expr);
- /* If it's still NULL, see if it is a complex expression, and if
- so, generate it recursively, otherwise, abort, because it's
- not really . */
- if (genop == NULL)
+ bitmap_iterator bi;
+ unsigned int i;
+
+ fprintf (out, " { ");
+ EXECUTE_IF_SET_IN_BITMAP (names, 0, i, bi)
{
- genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
- if (TREE_CODE_CLASS (TREE_CODE (genop)) != '1'
- && TREE_CODE_CLASS (TREE_CODE (genop)) != '2'
- && TREE_CODE_CLASS (TREE_CODE (genop)) != 'r')
- abort ();
- genop = create_expression_by_pieces (block, genop, stmts);
+ print_generic_expr (out, ssa_name (i), 0);
+ fprintf (out, " ");
}
- return genop;
+ fprintf (out, "}\n");
}
-
-/* Create an expression in pieces, so that we can handle very complex
+ /* Compute a set of representative vuse versions for each phi. This
+ is so we can compute conservative kill sets in terms of all vuses
+ that are killed, instead of continually walking chains.
+
+ We also have to be able kill all names associated with a phi when
+ the phi dies in order to ensure we don't generate overlapping
+ live ranges, which are not allowed in virtual SSA. */
+
+static bitmap *vuse_names;
+static void
+compute_vuse_representatives (void)
+{
+ tree phi;
+ basic_block bb;
+ VEC (tree, heap) *phis = NULL;
+ bool changed = true;
+ size_t i;
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb);
+ phi;
+ phi = PHI_CHAIN (phi))
+ if (!is_gimple_reg (PHI_RESULT (phi)))
+ VEC_safe_push (tree, heap, phis, phi);
+ }
+
+ while (changed)
+ {
+ changed = false;
+
+ for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
+ {
+ size_t ver = SSA_NAME_VERSION (PHI_RESULT (phi));
+ use_operand_p usep;
+ ssa_op_iter iter;
+
+ if (vuse_names[ver] == NULL)
+ {
+ vuse_names[ver] = BITMAP_ALLOC (&grand_bitmap_obstack);
+ bitmap_set_bit (vuse_names[ver], ver);
+ }
+ FOR_EACH_PHI_ARG (usep, phi, iter, SSA_OP_ALL_USES)
+ {
+ tree use = USE_FROM_PTR (usep);
+ bitmap usebitmap = get_representative (vuse_names,
+ SSA_NAME_VERSION (use));
+ if (usebitmap != NULL)
+ {
+ changed |= bitmap_ior_into (vuse_names[ver],
+ usebitmap);
+ }
+ else
+ {
+ changed |= !bitmap_bit_p (vuse_names[ver],
+ SSA_NAME_VERSION (use));
+ if (changed)
+ bitmap_set_bit (vuse_names[ver],
+ SSA_NAME_VERSION (use));
+ }
+ }
+ }
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
+ {
+ bitmap reps = get_representative (vuse_names,
+ SSA_NAME_VERSION (PHI_RESULT (phi)));
+ if (reps)
+ {
+ print_generic_expr (dump_file, PHI_RESULT (phi), 0);
+ fprintf (dump_file, " represents ");
+ dump_bitmap_of_names (dump_file, reps);
+ }
+ }
+ VEC_free (tree, heap, phis);
+}
+
+/* Compute reaching vuses 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.
+
+ 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.
+
+ An example:
+
+ <block begin>
+ b = *a
+ *a = 9
+ <block end>
+
+ b = *a is an antic safe load because it still safe to consider it
+ ANTIC at the top of the block.
+
+ 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. */
+
+static void
+compute_rvuse_and_antic_safe (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));
+ }
+
+ /* Compute local sets for reaching vuses.
+ GEN(block) = generated in block and not locally killed.
+ KILL(block) = set of vuses killed in block.
+ */
+
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator bsi;
+ ssa_op_iter iter;
+ def_operand_p defp;
+ use_operand_p usep;
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ 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)
+ {
+ tree def = DEF_FROM_PTR (defp);
+ bitmap_set_bit (RVUSE_GEN (bb), SSA_NAME_VERSION (def));
+ }
+ }
+ }
+
+ FOR_EACH_BB (bb)
+ {
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ if (!is_gimple_reg (PHI_RESULT (phi)))
+ {
+ edge e;
+ edge_iterator ei;
+
+ tree def = PHI_RESULT (phi);
+ /* In reality, the PHI result is generated at the end of
+ each predecessor block. This will make the value
+ LVUSE_IN for the bb containing the PHI, which is
+ correct. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ bitmap_set_bit (RVUSE_GEN (e->src), SSA_NAME_VERSION (def));
+ }
+ }
+ }
+
+ /* Solve reaching vuses.
+
+ RVUSE_IN[BB] = Union of RVUSE_OUT of predecessors.
+ RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB])
+ */
+ postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
+ pre_and_rev_post_order_compute (NULL, postorder, false);
+
+ changed = true;
+ while (changed)
+ {
+ int j;
+ changed = false;
+ for (j = 0; j < n_basic_blocks - NUM_FIXED_BLOCKS; j++)
+ {
+ edge e;
+ edge_iterator ei;
+ bb = BASIC_BLOCK (postorder[j]);
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ bitmap_ior_into (RVUSE_IN (bb), RVUSE_OUT (e->src));
+
+ changed |= bitmap_ior_and_compl (RVUSE_OUT (bb),
+ RVUSE_GEN (bb),
+ RVUSE_IN (bb),
+ RVUSE_KILL (bb));
+ }
+ }
+ free (postorder);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ FOR_ALL_BB (bb)
+ {
+ fprintf (dump_file, "RVUSE_IN (%d) =", bb->index);
+ dump_bitmap_of_names (dump_file, RVUSE_IN (bb));
+
+ fprintf (dump_file, "RVUSE_KILL (%d) =", bb->index);
+ dump_bitmap_of_names (dump_file, RVUSE_KILL (bb));
+
+ fprintf (dump_file, "RVUSE_GEN (%d) =", bb->index);
+ dump_bitmap_of_names (dump_file, RVUSE_GEN (bb));
+
+ fprintf (dump_file, "RVUSE_OUT (%d) =", bb->index);
+ dump_bitmap_of_names (dump_file, RVUSE_OUT (bb));
+ }
+ }
+
+ FOR_EACH_BB (bb)
+ {
+ value_set_node_t node;
+ if (bitmap_empty_p (RVUSE_KILL (bb)))
+ continue;
+
+ for (node = EXP_GEN (bb)->head; node; node = node->next)
+ {
+ if (REFERENCE_CLASS_P (node->expr))
+ {
+ tree vh = get_value_handle (node->expr);
+ tree maybe = bitmap_find_leader (AVAIL_OUT (bb), vh);
+
+ if (maybe)
+ {
+ 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);
+ }
+ }
+ }
+ }
+ }
+ free (first_store_uid);
+}
+
+/* Return true if we can value number the call in STMT. This is true
+ if we have a pure or constant call. */
+
+static bool
+can_value_number_call (tree stmt)
+{
+ tree call = get_call_expr_in (stmt);
+
+ if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
+ return true;
+ return false;
+}
+
+/* Return true if OP is a tree which we can perform value numbering
+ on. */
+
+static bool
+can_value_number_operation (tree op)
+{
+ return UNARY_CLASS_P (op)
+ || BINARY_CLASS_P (op)
+ || COMPARISON_CLASS_P (op)
+ || REFERENCE_CLASS_P (op)
+ || (TREE_CODE (op) == CALL_EXPR
+ && can_value_number_call (op));
+}
+
+
+/* Return true if OP is a tree which we can perform PRE on
+ on. This may not match the operations we can value number, but in
+ a perfect world would. */
+
+static bool
+can_PRE_operation (tree op)
+{
+ return UNARY_CLASS_P (op)
+ || BINARY_CLASS_P (op)
+ || COMPARISON_CLASS_P (op)
+ || TREE_CODE (op) == INDIRECT_REF
+ || TREE_CODE (op) == COMPONENT_REF
+ || TREE_CODE (op) == CALL_EXPR
+ || TREE_CODE (op) == ARRAY_REF;
+}
+
+
+/* Inserted expressions are placed onto this worklist, which is used
+ for performing quick dead code elimination of insertions we made
+ that didn't turn out to be necessary. */
+static VEC(tree,heap) *inserted_exprs;
+
+/* Pool allocated fake store expressions are placed onto this
+ worklist, which, after performing dead code elimination, is walked
+ to see which expressions need to be put into GC'able memory */
+static VEC(tree, heap) *need_creation;
+
+/* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
+ COMPONENT_REF or INDIRECT_REF or ARRAY_REF portion, because we'd end up with
+ trying to rename aggregates into ssa form directly, which is a no
+ no.
+
+ Thus, this routine doesn't create temporaries, it just builds a
+ single access expression for the array, calling
+ find_or_generate_expression to build the innermost pieces.
+
+ This function is a subroutine of create_expression_by_pieces, and
+ should not be called on it's own unless you really know what you
+ are doing.
+*/
+static tree
+create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
+{
+ tree genop = expr;
+ tree folded;
+
+ if (TREE_CODE (genop) == VALUE_HANDLE)
+ {
+ tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
+ if (found)
+ return found;
+ }
+
+ if (TREE_CODE (genop) == VALUE_HANDLE)
+ genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
+
+ switch TREE_CODE (genop)
+ {
+ case ARRAY_REF:
+ {
+ tree op0;
+ tree op1, op2, op3;
+ op0 = create_component_ref_by_pieces (block,
+ TREE_OPERAND (genop, 0),
+ stmts);
+ op1 = TREE_OPERAND (genop, 1);
+ if (TREE_CODE (op1) == VALUE_HANDLE)
+ op1 = find_or_generate_expression (block, op1, stmts);
+ op2 = TREE_OPERAND (genop, 2);
+ if (op2 && TREE_CODE (op2) == VALUE_HANDLE)
+ op2 = find_or_generate_expression (block, op2, stmts);
+ op3 = TREE_OPERAND (genop, 3);
+ if (op3 && TREE_CODE (op3) == VALUE_HANDLE)
+ op3 = find_or_generate_expression (block, op3, stmts);
+ folded = build4 (ARRAY_REF, TREE_TYPE (genop), op0, op1,
+ op2, op3);
+ return folded;
+ }
+ case COMPONENT_REF:
+ {
+ tree op0;
+ tree op1;
+ op0 = create_component_ref_by_pieces (block,
+ TREE_OPERAND (genop, 0),
+ stmts);
+ op1 = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (genop, 1))->head->expr;
+ folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1,
+ NULL_TREE);
+ return folded;
+ }
+ break;
+ case INDIRECT_REF:
+ {
+ tree op1 = TREE_OPERAND (genop, 0);
+ tree genop1 = find_or_generate_expression (block, op1, stmts);
+
+ folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
+ genop1);
+ return folded;
+ }
+ break;
+ case VAR_DECL:
+ case PARM_DECL:
+ case RESULT_DECL:
+ case SSA_NAME:
+ case STRING_CST:
+ return genop;
+ default:
+ gcc_unreachable ();
+ }
+
+ return NULL_TREE;
+}
+
+/* Find a leader for an expression, or generate one using
+ create_expression_by_pieces if it's ANTIC but
+ complex.
+ BLOCK is the basic_block we are looking for leaders in.
+ EXPR is the expression to find a leader or generate for.
+ STMTS is the statement list to put the inserted expressions on.
+ Returns the SSA_NAME of the LHS of the generated expression or the
+ leader. */
+
+static tree
+find_or_generate_expression (basic_block block, tree expr, tree stmts)
+{
+ tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
+
+ /* If it's still NULL, it must be a complex expression, so generate
+ it recursively. */
+ if (genop == NULL)
+ {
+ genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
+
+ gcc_assert (can_PRE_operation (genop));
+ genop = create_expression_by_pieces (block, genop, stmts);
+ }
+ return genop;
+}
+
+#define NECESSARY(stmt) stmt->common.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,
EXPR is the expression to insert (in value form)
STMTS is a statement list to append the necessary insertions into.
- This function will abort if we hit some value that shouldn't be
+ This function will die if we hit some value that shouldn't be
ANTIC but is (IE there is no leader for it, or its components).
This function may also generate expressions that are themselves
partially or fully redundant. Those that are will be either made
static tree
create_expression_by_pieces (basic_block block, tree expr, tree stmts)
{
- tree name = NULL_TREE;
- tree newexpr = NULL_TREE;
+ tree temp, name;
+ tree folded, forced_stmts, newexpr;
tree v;
-
+ tree_stmt_iterator tsi;
+
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
- case '2':
+ case tcc_expression:
+ {
+ tree op0, op2;
+ tree arglist;
+ tree genop0, genop2;
+ tree genarglist;
+ tree walker, genwalker;
+
+ gcc_assert (TREE_CODE (expr) == CALL_EXPR);
+ genop2 = NULL;
+
+ op0 = TREE_OPERAND (expr, 0);
+ arglist = TREE_OPERAND (expr, 1);
+ op2 = TREE_OPERAND (expr, 2);
+
+ 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))
+ {
+ TREE_VALUE (genwalker)
+ = find_or_generate_expression (block, TREE_VALUE (walker),
+ stmts);
+ }
+
+ if (op2)
+ genop2 = find_or_generate_expression (block, op2, stmts);
+ folded = fold_build3 (TREE_CODE (expr), TREE_TYPE (expr),
+ genop0, genarglist, genop2);
+ break;
+
+
+ }
+ break;
+ case tcc_reference:
+ {
+ if (TREE_CODE (expr) == COMPONENT_REF
+ || TREE_CODE (expr) == ARRAY_REF)
+ {
+ folded = create_component_ref_by_pieces (block, expr, stmts);
+ }
+ else
+ {
+ tree op1 = TREE_OPERAND (expr, 0);
+ tree genop1 = find_or_generate_expression (block, op1, stmts);
+
+ folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
+ genop1);
+ }
+ break;
+ }
+
+ case tcc_binary:
+ case tcc_comparison:
{
- tree_stmt_iterator tsi;
- tree genop1, genop2;
- tree temp;
tree op1 = TREE_OPERAND (expr, 0);
tree op2 = TREE_OPERAND (expr, 1);
- genop1 = find_or_generate_expression (block, op1, stmts);
- genop2 = find_or_generate_expression (block, op2, stmts);
- temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
- add_referenced_tmp_var (temp);
- newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
- genop1, genop2);
- newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
- temp, newexpr);
- name = make_ssa_name (temp, newexpr);
- TREE_OPERAND (newexpr, 0) = name;
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
- pre_stats.insertions++;
+ tree genop1 = find_or_generate_expression (block, op1, stmts);
+ tree genop2 = find_or_generate_expression (block, op2, stmts);
+ folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
+ genop1, genop2);
break;
}
- case '1':
+
+ case tcc_unary:
{
- tree_stmt_iterator tsi;
- tree genop1;
- tree temp;
tree op1 = TREE_OPERAND (expr, 0);
- genop1 = find_or_generate_expression (block, op1, stmts);
- temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
- add_referenced_tmp_var (temp);
- newexpr = build (TREE_CODE (expr), TREE_TYPE (expr),
- genop1);
- newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
- temp, newexpr);
- name = make_ssa_name (temp, newexpr);
- TREE_OPERAND (newexpr, 0) = name;
- tsi = tsi_last (stmts);
- tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
- pre_stats.insertions++;
-
+ tree genop1 = find_or_generate_expression (block, op1, stmts);
+ folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
+ genop1);
break;
}
+
default:
- abort ();
-
+ gcc_unreachable ();
+ }
+
+ /* Force the generated expression to be a sequence of GIMPLE
+ statements.
+ 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);
+
+ /* If we have any intermediate expressions to the value sets, add them
+ to the value sets and chain them on in the instruction stream. */
+ if (forced_stmts)
+ {
+ tsi = tsi_start (forced_stmts);
+ 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);
+
+ VEC_safe_push (tree, heap, inserted_exprs, stmt);
+ 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);
+ }
+ tsi = tsi_last (stmts);
+ tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
+ }
+
+ /* Build and insert the assignment of the end result to the temporary
+ that we will return. */
+ if (!pretemp || TREE_TYPE (expr) != TREE_TYPE (pretemp))
+ {
+ pretemp = create_tmp_var (TREE_TYPE (expr), "pretmp");
+ get_var_ann (pretemp);
}
+
+ temp = pretemp;
+ add_referenced_var (temp);
+
+ if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
+ DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
+
+ newexpr = build2 (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr);
+ name = make_ssa_name (temp, newexpr);
+ TREE_OPERAND (newexpr, 0) = name;
+ NECESSARY (newexpr) = 0;
+
+ tsi = tsi_last (stmts);
+ tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
+ VEC_safe_push (tree, heap, inserted_exprs, newexpr);
+ mark_new_vars_to_rename (newexpr);
+
+ /* Add a value handle to the temporary.
+ The value may already exist in either NEW_SETS, or AVAIL_OUT, because
+ we are creating the expression by pieces, and this particular piece of
+ the expression may have been represented. There is no harm in replacing
+ here. */
v = get_value_handle (expr);
- vn_add (name, v, NULL);
- bitmap_insert_into_set (NEW_SETS (block), name);
- bitmap_value_insert_into_set (AVAIL_OUT (block), name);
+ vn_add (name, v);
+ bitmap_value_replace_in_set (NEW_SETS (block), name);
+ bitmap_value_replace_in_set (AVAIL_OUT (block), name);
+
+ pre_stats.insertions++;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Inserted ");
print_generic_expr (dump_file, newexpr, 0);
fprintf (dump_file, " in predecessor %d\n", block->index);
}
+
return name;
}
+
+/* Insert the to-be-made-available values of NODE for each
+ predecessor, stored in AVAIL, into the predecessors of BLOCK, and
+ merge the result with a phi node, given the same value handle as
+ NODE. Return true if we have inserted new stuff. */
+
+static bool
+insert_into_preds_of_block (basic_block block, value_set_node_t node,
+ tree *avail)
+{
+ tree val = get_value_handle (node->expr);
+ edge pred;
+ bool insertions = false;
+ bool nophi = false;
+ basic_block bprime;
+ tree eprime;
+ edge_iterator ei;
+ tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
+ tree temp;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found partial redundancy for expression ");
+ print_generic_expr (dump_file, node->expr, 0);
+ fprintf (dump_file, " (");
+ print_generic_expr (dump_file, val, 0);
+ fprintf (dump_file, ")");
+ fprintf (dump_file, "\n");
+ }
+
+ /* Make sure we aren't creating an induction variable. */
+ if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2
+ && TREE_CODE_CLASS (TREE_CODE (node->expr)) != tcc_reference )
+ {
+ bool firstinsideloop = false;
+ bool secondinsideloop = false;
+ firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
+ EDGE_PRED (block, 0)->src);
+ secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
+ EDGE_PRED (block, 1)->src);
+ /* Induction variables only have one edge inside the loop. */
+ if (firstinsideloop ^ secondinsideloop)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
+ nophi = true;
+ }
+ }
+
+
+ /* Make the necessary insertions. */
+ FOR_EACH_EDGE (pred, ei, block->preds)
+ {
+ tree stmts = alloc_stmt_list ();
+ tree builtexpr;
+ bprime = pred->src;
+ eprime = avail[bprime->index];
+
+ 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);
+ bsi_insert_on_edge (pred, stmts);
+ avail[bprime->index] = builtexpr;
+ insertions = true;
+ }
+ }
+ /* If we didn't want a phi node, and we made insertions, we still have
+ inserted new stuff, and thus return true. If we didn't want a phi node,
+ and didn't make insertions, we haven't added anything new, so return
+ false. */
+ if (nophi && insertions)
+ return true;
+ else if (nophi && !insertions)
+ return false;
+
+ /* Now build a phi for the new variable. */
+ if (!prephitemp || TREE_TYPE (prephitemp) != type)
+ {
+ prephitemp = create_tmp_var (type, "prephitmp");
+ get_var_ann (prephitemp);
+ }
+
+ temp = prephitemp;
+ add_referenced_var (temp);
+
+ if (TREE_CODE (type) == COMPLEX_TYPE)
+ DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
+ temp = create_phi_node (temp, block);
+
+ NECESSARY (temp) = 0;
+ VEC_safe_push (tree, heap, inserted_exprs, temp);
+ FOR_EACH_EDGE (pred, ei, block->preds)
+ add_phi_arg (temp, avail[pred->src->index], pred);
+
+ vn_add (PHI_RESULT (temp), val);
+
+ /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
+ this insertion, since we test for the existence of this value in PHI_GEN
+ before proceeding with the partial redundancy checks in insert_aux.
+
+ The value may exist in AVAIL_OUT, in particular, it could be represented
+ by the expression we are trying to eliminate, in which case we want the
+ replacement to occur. If it's not existing in AVAIL_OUT, we want it
+ inserted there.
+
+ Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
+ this block, because if it did, it would have existed in our dominator's
+ AVAIL_OUT, and would have been skipped due to the full redundancy check.
+ */
+
+ bitmap_insert_into_set (PHI_GEN (block),
+ PHI_RESULT (temp));
+ bitmap_value_replace_in_set (AVAIL_OUT (block),
+ PHI_RESULT (temp));
+ bitmap_insert_into_set (NEW_SETS (block),
+ PHI_RESULT (temp));
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Created phi ");
+ print_generic_expr (dump_file, temp, 0);
+ fprintf (dump_file, " in block %d\n", block->index);
+ }
+ pre_stats.phis++;
+ return true;
+}
+
+
/* Perform insertion of partially redundant values.
For BLOCK, do the following:
3. Recursively call ourselves on the dominator children of BLOCK.
*/
+
static bool
insert_aux (basic_block block)
{
dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
{
- int i;
+ unsigned i;
+ bitmap_iterator bi;
bitmap_set_t newset = NEW_SETS (dom);
- EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i,
- {
- bitmap_insert_into_set (NEW_SETS (block), ssa_name (i));
- bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
- });
- if (block->pred->pred_next)
+ if (newset)
+ {
+ /* Note that we need to value_replace both NEW_SETS, and
+ 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)
+ {
+ bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
+ bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
+ }
+ }
+ if (!single_pred_p (block))
{
value_set_node_t node;
for (node = ANTIC_IN (block)->head;
node;
node = node->next)
{
- if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
- || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
+ if (can_PRE_operation (node->expr)
+ && !AGGREGATE_TYPE_P (TREE_TYPE (node->expr)))
{
tree *avail;
tree val;
tree first_s = NULL;
edge pred;
basic_block bprime;
- tree eprime;
+ tree eprime = NULL_TREE;
+ edge_iterator ei;
val = get_value_handle (node->expr);
if (bitmap_set_contains_value (PHI_GEN (block), val))
fprintf (dump_file, "Found fully redundant value\n");
continue;
}
-
- avail = xcalloc (last_basic_block, sizeof (tree));
- for (pred = block->pred;
- pred;
- pred = pred->pred_next)
+
+ avail = XCNEWVEC (tree, last_basic_block);
+ FOR_EACH_EDGE (pred, ei, block->preds)
{
tree vprime;
tree edoubleprime;
break;
}
+ eprime = fully_constant_expression (eprime);
vprime = get_value_handle (eprime);
- if (!vprime)
- abort ();
+ gcc_assert (vprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
vprime);
if (edoubleprime == NULL)
by_some = true;
if (first_s == NULL)
first_s = edoubleprime;
- else if (first_s != edoubleprime)
+ else if (!operand_equal_p (first_s, edoubleprime,
+ 0))
all_same = false;
- if (first_s != edoubleprime
- && operand_equal_p (first_s, edoubleprime, 0))
- abort ();
}
}
/* If we can insert it, it's not the same value
partially redundant. */
if (!cant_insert && !all_same && by_some)
{
- tree type = TREE_TYPE (avail[block->pred->src->index]);
- tree temp;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Found partial redundancy for expression ");
- print_generic_expr (dump_file, node->expr, 0);
- fprintf (dump_file, "\n");
- }
+ 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);
+ }
+ }
+ }
+ }
+ }
+ for (son = first_dom_son (CDI_DOMINATORS, block);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ {
+ new_stuff |= insert_aux (son);
+ }
+
+ return new_stuff;
+}
+
+/* Perform insertion of partially redundant values. */
+
+static void
+insert (void)
+{
+ bool new_stuff = true;
+ basic_block bb;
+ int num_iterations = 0;
+
+ FOR_ALL_BB (bb)
+ NEW_SETS (bb) = bitmap_set_new ();
+
+ while (new_stuff)
+ {
+ num_iterations++;
+ new_stuff = false;
+ new_stuff = insert_aux (ENTRY_BLOCK_PTR);
+ }
+ if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, "insert required %d iterations\n", num_iterations);
+}
+
+
+/* Return true if VAR is an SSA variable with no defining statement in
+ this procedure, *AND* isn't a live-on-entry parameter. */
+
+static bool
+is_undefined_value (tree expr)
+{
+ return (TREE_CODE (expr) == SSA_NAME
+ && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
+ /* PARM_DECLs and hard registers are always defined. */
+ && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
+}
+
+
+/* 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.
+
+ VUSES represent the virtual use operands associated with EXPR (if
+ any). */
+
+static inline void
+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);
+
+ /* VAR and EXPR may be the same when processing statements for which
+ we are not computing value numbers (e.g., non-assignments, or
+ statements that make aliased stores). In those cases, we are
+ only interested in making VAR available as its own value. */
+ if (var != expr)
+ vn_add (var, val);
+
+ if (s1)
+ bitmap_insert_into_set (s1, var);
+ bitmap_value_insert_into_set (s2, var);
+}
+
+
+/* Given a unary or binary expression EXPR, create and return a new
+ expression with the same structure as EXPR but with its operands
+ replaced with the value handles of each of the operands of EXPR.
+
+ VUSES represent the virtual use operands associated with EXPR (if
+ any). Insert EXPR's operands into the EXP_GEN set for BLOCK. */
+
+static inline tree
+create_value_expr_from (tree expr, basic_block block, tree stmt)
+{
+ int i;
+ enum tree_code code = TREE_CODE (expr);
+ tree vexpr;
+ alloc_pool pool;
+
+ 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_exceptional
+ || TREE_CODE_CLASS (code) == tcc_declaration);
+
+ if (TREE_CODE_CLASS (code) == tcc_unary)
+ pool = unary_node_pool;
+ else if (TREE_CODE_CLASS (code) == tcc_reference)
+ pool = reference_node_pool;
+ else if (TREE_CODE_CLASS (code) == tcc_binary)
+ 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));
+
+ /* 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)
+ {
+ 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;
+ }
+
+ for (i = 0; i < TREE_CODE_LENGTH (code); i++)
+ {
+ tree val, op;
+
+ op = TREE_OPERAND (expr, i);
+ if (op == NULL_TREE)
+ continue;
+
+ /* Recursively value-numberize reference ops and tree lists. */
+ if (REFERENCE_CLASS_P (op))
+ {
+ tree tempop = create_value_expr_from (op, block, stmt);
+ op = tempop ? tempop : op;
+ val = vn_lookup_or_add (op, stmt);
+ }
+ else if (TREE_CODE (op) == TREE_LIST)
+ {
+ 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;
+ }
+ 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 (val) == VALUE_HANDLE)
+ TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
+
+ TREE_OPERAND (vexpr, i) = val;
+ }
+
+ 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;
- /* Make the necessary insertions. */
- for (pred = block->pred;
- pred;
- pred = pred->pred_next)
- {
- tree stmts = alloc_stmt_list ();
- tree builtexpr;
- bprime = pred->src;
- eprime = avail[bprime->index];
- if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2'
- || TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
- {
- builtexpr = create_expression_by_pieces (bprime,
- eprime,
- stmts);
- bsi_insert_on_edge (pred, stmts);
- bsi_commit_edge_inserts (NULL);
- avail[bprime->index] = builtexpr;
- }
- }
- /* Now build a phi for the new variable. */
- temp = create_tmp_var (type, "prephitmp");
- add_referenced_tmp_var (temp);
- temp = create_phi_node (temp, block);
- vn_add (PHI_RESULT (temp), val, NULL);
-
-#if 0
- if (!set_contains_value (AVAIL_OUT (block), val))
- insert_into_set (AVAIL_OUT (block),
- PHI_RESULT (temp));
- else
-#endif
- bitmap_value_replace_in_set (AVAIL_OUT (block),
- PHI_RESULT (temp));
- for (pred = block->pred;
- pred;
- pred = pred->pred_next)
- {
- add_phi_arg (&temp, avail[pred->src->index],
- pred);
- }
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Created phi ");
- print_generic_expr (dump_file, temp, 0);
- fprintf (dump_file, " in block %d\n", block->index);
- }
- pre_stats.phis++;
- new_stuff = true;
- bitmap_insert_into_set (NEW_SETS (block),
- PHI_RESULT (temp));
- bitmap_insert_into_set (PHI_GEN (block),
- PHI_RESULT (temp));
- }
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+ continue;
- free (avail);
+ 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");
}
}
}
- for (son = first_dom_son (CDI_DOMINATORS, block);
- son;
- son = next_dom_son (CDI_DOMINATORS, son))
+}
+
+/* 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)
{
- new_stuff |= insert_aux (son);
+ 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;
+ }
}
- return new_stuff;
+ /* 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;
}
-/* Perform insertion of partially redundant values. */
+/* Return a copy of NODE that is stored in the temporary alloc_pool's.
+ This is made recursively true, so that the operands are stored in
+ the pool as well. */
-static void
-insert (void)
+static tree
+poolify_tree (tree node)
{
- bool new_stuff = true;
- basic_block bb;
- int num_iterations = 0;
-
- FOR_ALL_BB (bb)
- NEW_SETS (bb) = bitmap_set_new ();
-
- while (new_stuff)
+ switch (TREE_CODE (node))
{
- num_iterations++;
- new_stuff = false;
- new_stuff = insert_aux (ENTRY_BLOCK_PTR);
+ case INDIRECT_REF:
+ {
+ tree temp = pool_alloc (reference_node_pool);
+ memcpy (temp, node, tree_size (node));
+ TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
+ return temp;
+ }
+ break;
+ case MODIFY_EXPR:
+ {
+ tree temp = pool_alloc (modify_expr_node_pool);
+ memcpy (temp, node, tree_size (node));
+ TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
+ TREE_OPERAND (temp, 1) = poolify_tree (TREE_OPERAND (temp, 1));
+ return temp;
+ }
+ break;
+ case SSA_NAME:
+ case INTEGER_CST:
+ case STRING_CST:
+ case REAL_CST:
+ case PARM_DECL:
+ case VAR_DECL:
+ case RESULT_DECL:
+ return node;
+ default:
+ gcc_unreachable ();
}
- if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
- fprintf (dump_file, "insert required %d iterations\n", num_iterations);
}
+static tree modify_expr_template;
-/* Return true if VAR is an SSA variable with no defining statement in
- this procedure, *AND* isn't a live-on-entry parameter. */
-
-static bool
-is_undefined_value (tree expr)
+/* Allocate a MODIFY_EXPR with TYPE, and operands OP1, OP2 in the
+ alloc pools and return it. */
+static tree
+poolify_modify_expr (tree type, tree op1, tree op2)
{
- return (TREE_CODE (expr) == SSA_NAME
- && IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
- /* PARM_DECLs and hard registers are always defined. */
- && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL
- && !DECL_HARD_REGISTER (SSA_NAME_VAR (expr)));
+ if (modify_expr_template == NULL)
+ modify_expr_template = build2 (MODIFY_EXPR, type, op1, op2);
+
+ TREE_OPERAND (modify_expr_template, 0) = op1;
+ TREE_OPERAND (modify_expr_template, 1) = op2;
+ TREE_TYPE (modify_expr_template) = type;
+
+ return poolify_tree (modify_expr_template);
}
-/* 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.
+/* For each real store operation of the form
+ *a = <value> that we see, create a corresponding fake store of the
+ form storetmp_<version> = *a.
- VUSES represent the virtual use operands associated with EXPR (if
- any). They are used when computing the hash value for EXPR. */
+ This enables AVAIL computation to mark the results of stores as
+ available. Without this, you'd need to do some computation to
+ mark the result of stores as ANTIC and AVAIL at all the right
+ points.
+ To save memory, we keep the store
+ statements pool allocated until we decide whether they are
+ necessary or not. */
-static inline void
-add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1,
- bitmap_set_t s2)
+static void
+insert_fake_stores (void)
{
- tree val = vn_lookup_or_add (expr, vuses);
+ basic_block block;
- /* VAR and EXPR may be the same when processing statements for which
- we are not computing value numbers (e.g., non-assignments, or
- statements that make aliased stores). In those cases, we are
- only interested in making VAR available as its own value. */
- if (var != expr)
- vn_add (var, val, NULL);
+ FOR_ALL_BB (block)
+ {
+ block_stmt_iterator bsi;
+ for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
- bitmap_insert_into_set (s1, var);
- bitmap_value_insert_into_set (s2, var);
-}
+ /* We can't generate SSA names for stores that are complex
+ or aggregate. We also want to ignore things whose
+ virtual uses occur in abnormal phis. */
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == INDIRECT_REF
+ && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 0)))
+ && TREE_CODE (TREE_TYPE (TREE_OPERAND (stmt, 0))) != COMPLEX_TYPE)
+ {
+ ssa_op_iter iter;
+ def_operand_p defp;
+ tree lhs = TREE_OPERAND (stmt, 0);
+ tree rhs = TREE_OPERAND (stmt, 1);
+ tree new;
+ bool notokay = false;
-/* Given a unary or binary expression EXPR, create and return a new
- expression with the same structure as EXPR but with its operands
- replaced with the value handles of each of the operands of EXPR.
- Insert EXPR's operands into the EXP_GEN set for BLOCK.
+ FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+ {
+ tree defvar = DEF_FROM_PTR (defp);
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
+ {
+ notokay = true;
+ break;
+ }
+ }
- VUSES represent the virtual use operands associated with EXPR (if
- any). They are used when computing the hash value for EXPR. */
+ if (notokay)
+ continue;
-static inline tree
-create_value_expr_from (tree expr, basic_block block, vuse_optype vuses)
-{
- int i;
- enum tree_code code = TREE_CODE (expr);
- tree vexpr;
+ if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
+ {
+ storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
+ get_var_ann (storetemp);
+ }
-#if defined ENABLE_CHECKING
- if (TREE_CODE_CLASS (code) != '1'
- && TREE_CODE_CLASS (code) != '2'
- && TREE_CODE_CLASS (code) != 'r')
- abort ();
-#endif
+ new = poolify_modify_expr (TREE_TYPE (stmt), storetemp, lhs);
- if (TREE_CODE_CLASS (code) == '1')
- vexpr = pool_alloc (unary_node_pool);
- else if (TREE_CODE_CLASS (code) == 'r')
- vexpr = pool_alloc (reference_node_pool);
- else
- vexpr = pool_alloc (binary_node_pool);
+ lhs = make_ssa_name (storetemp, new);
+ TREE_OPERAND (new, 0) = lhs;
+ create_ssa_artficial_load_stmt (new, stmt);
- memcpy (vexpr, expr, tree_size (expr));
+ 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);
+ }
+ }
+ }
+}
- for (i = 0; i < TREE_CODE_LENGTH (code); i++)
+/* Turn the pool allocated fake stores that we created back into real
+ GC allocated ones if they turned out to be necessary to PRE some
+ expressions. */
+
+static void
+realify_fake_stores (void)
+{
+ unsigned int i;
+ tree stmt;
+
+ for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
{
- tree op = TREE_OPERAND (expr, i);
- if (op != NULL)
+ if (NECESSARY (stmt))
{
- tree val = vn_lookup_or_add (op, vuses);
- if (!is_undefined_value (op))
- value_insert_into_set (EXP_GEN (block), op);
- TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
- TREE_OPERAND (vexpr, i) = val;
+ block_stmt_iterator bsi;
+ tree newstmt;
+
+ /* Mark the temp variable as referenced */
+ add_referenced_var (SSA_NAME_VAR (TREE_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
+ the old statement before the store in the IR stream
+ 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;
+ bsi_insert_before (&bsi, newstmt, BSI_SAME_STMT);
+ bsi = bsi_for_stmt (stmt);
+ bsi_remove (&bsi, true);
}
+ else
+ release_defs (stmt);
}
+}
- return vexpr;
+/* 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. */
+
+static bool
+try_combine_conversion (tree *expr_p)
+{
+ tree expr = *expr_p;
+ tree t;
+
+ 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;
+
+ t = fold_unary (TREE_CODE (expr), TREE_TYPE (expr),
+ VALUE_HANDLE_EXPR_SET (TREE_OPERAND (expr, 0))->head->expr);
+
+ /* Disallow value expressions we have no value number for already, as
+ we would miss a leader for it here. */
+ if (t
+ && !(TREE_CODE (t) == VALUE_HANDLE
+ || is_gimple_min_invariant (t)))
+ t = vn_lookup (t, NULL);
+
+ if (t && t != expr)
+ {
+ *expr_p = t;
+ return true;
+ }
+ return false;
}
+/* Compute the AVAIL set for all basic blocks.
-/* Compute the AVAIL set for BLOCK.
- This function performs value numbering of the statements in BLOCK.
- The AVAIL sets are built from information we glean while doing this
- value numbering, since the AVAIL sets contain only one entry per
+ This function performs value numbering of the statements in each basic
+ block. The AVAIL sets are built from information we glean while doing
+ this value numbering, since the AVAIL sets contain only one entry per
value.
AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
static void
-compute_avail (basic_block block)
+compute_avail (void)
{
- basic_block son;
-
+ basic_block block, son;
+ basic_block *worklist;
+ size_t sp = 0;
+ tree param;
/* For arguments with default definitions, we pretend they are
defined in the entry block. */
- if (block == ENTRY_BLOCK_PTR)
+ for (param = DECL_ARGUMENTS (current_function_decl);
+ param;
+ param = TREE_CHAIN (param))
{
- tree param;
- for (param = DECL_ARGUMENTS (current_function_decl);
- param;
- param = TREE_CHAIN (param))
+ if (default_def (param) != NULL)
{
- if (default_def (param) != NULL)
- {
- tree val;
- tree def = default_def (param);
- val = vn_lookup_or_add (def, NULL);
- bitmap_insert_into_set (TMP_GEN (block), def);
- bitmap_value_insert_into_set (AVAIL_OUT (block), def);
- }
+ 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);
}
}
- else if (block)
+
+ /* Likewise for the static chain decl. */
+ 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);
+ }
+ }
+
+ /* Allocate the worklist. */
+ worklist = XNEWVEC (basic_block, n_basic_blocks);
+
+ /* Seed the algorithm by putting the dominator children of the entry
+ block on the worklist. */
+ for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ worklist[sp++] = son;
+
+ /* Loop until the worklist is empty. */
+ while (sp)
{
block_stmt_iterator bsi;
tree stmt, phi;
basic_block dom;
+ unsigned int stmt_uid = 1;
+
+ /* Pick a block from the worklist. */
+ block = worklist[--sp];
/* Initially, the set of available values in BLOCK is that of
its immediate dominator. */
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
for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt_ann_t ann;
- size_t j;
+ ssa_op_iter iter;
+ tree op;
stmt = bsi_stmt (bsi);
ann = stmt_ann (stmt);
- get_stmt_operands (stmt);
+
+ ann->uid = stmt_uid++;
- /* We are only interested in assignments of the form
- X_i = EXPR, where EXPR represents an "interesting"
- computation, it has no volatile operands and X_i
- doesn't flow through an abnormal edge. */
+ /* For regular value numbering, we are only interested in
+ assignments of the form X_i = EXPR, where EXPR represents
+ an "interesting" computation, it has no volatile operands
+ and X_i doesn't flow through an abnormal edge. */
if (TREE_CODE (stmt) == MODIFY_EXPR
&& !ann->has_volatile_ops
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
{
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
- vuse_optype vuses = STMT_VUSE_OPS (stmt);
+
+ /* 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;
STRIP_USELESS_TYPE_CONVERSION (rhs);
- if (TREE_CODE (rhs) == SSA_NAME
- || is_gimple_min_invariant (rhs))
+ if (can_value_number_operation (rhs))
+ {
+ /* For value numberable operation, create a
+ duplicate expression with the operands replaced
+ with the value handles of the original RHS. */
+ tree newt = create_value_expr_from (rhs, block, stmt);
+ if (newt)
+ {
+ /* If we can combine a conversion expression
+ with the expression for its operand just
+ record the value number for it. */
+ if (try_combine_conversion (&newt))
+ vn_add (lhs, newt);
+ else
+ {
+ tree val = vn_lookup_or_add (newt, stmt);
+ vn_add (lhs, val);
+ value_insert_into_set (EXP_GEN (block), newt);
+ }
+ bitmap_insert_into_set (TMP_GEN (block), lhs);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), lhs);
+ continue;
+ }
+ }
+ else if ((TREE_CODE (rhs) == SSA_NAME
+ && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
+ || is_gimple_min_invariant (rhs)
+ || TREE_CODE (rhs) == ADDR_EXPR
+ || TREE_INVARIANT (rhs)
+ || DECL_P (rhs))
{
/* Compute a value number for the RHS of the statement
and add its value to the AVAIL_OUT set for the block.
Add the LHS to TMP_GEN. */
- add_to_sets (lhs, rhs, vuses, TMP_GEN (block),
+ add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
AVAIL_OUT (block));
if (TREE_CODE (rhs) == SSA_NAME
value_insert_into_set (EXP_GEN (block), rhs);
continue;
}
- else if (TREE_CODE_CLASS (TREE_CODE (rhs)) == '1'
- || TREE_CODE_CLASS (TREE_CODE (rhs)) == '2'
- || TREE_CODE (rhs) == INDIRECT_REF)
- {
- /* For binary, unary, and reference expressions,
- create a duplicate expression with the operands
- replaced with the value handles of the original
- RHS. */
- tree newt = create_value_expr_from (rhs, block, vuses);
- add_to_sets (lhs, newt, vuses, TMP_GEN (block),
- AVAIL_OUT (block));
- value_insert_into_set (EXP_GEN (block), newt);
- continue;
- }
}
/* For any other statement that we don't recognize, simply
make the names generated by the statement available in
AVAIL_OUT and TMP_GEN. */
- for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
- {
- tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
- add_to_sets (def, def, NULL, TMP_GEN (block),
- AVAIL_OUT (block));
- }
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
+ add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
- for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
- {
- tree use = USE_OP (STMT_USE_OPS (stmt), j);
- add_to_sets (use, use, 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));
}
+
+ /* Put the dominator children of BLOCK on the worklist of blocks
+ to compute available sets for. */
+ for (son = first_dom_son (CDI_DOMINATORS, block);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ worklist[sp++] = son;
}
- /* Compute available sets for the dominator children of BLOCK. */
- for (son = first_dom_son (CDI_DOMINATORS, block);
- son;
- son = next_dom_son (CDI_DOMINATORS, son))
- compute_avail (son);
+ free (worklist);
}
&& (TREE_CODE (*rhs_p) != SSA_NAME
|| may_propagate_copy (*rhs_p, sprime)))
{
- if (sprime == *rhs_p)
- abort ();
+ gcc_assert (sprime != *rhs_p);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " in ");
print_generic_stmt (dump_file, stmt, 0);
}
+
+ if (TREE_CODE (sprime) == SSA_NAME)
+ NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
+ /* We need to make sure the new and old types actually match,
+ 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)))
+ sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
+
pre_stats.eliminations++;
propagate_tree_value (rhs_p, sprime);
- modify_stmt (stmt);
+ update_stmt (stmt);
/* If we removed EH side effects from the statement, clean
its EH information. */
- if (maybe_clean_eh_stmt (stmt))
+ if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
{
bitmap_set_bit (need_eh_cleanup,
bb_for_stmt (stmt)->index);
}
}
+/* Borrow a bit of tree-ssa-dce.c for the moment.
+ XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
+ this may be a bit faster, and we may want critical edges kept split. */
+
+/* If OP's defining statement has not already been determined to be necessary,
+ mark that statement necessary. Return the stmt, if it is newly
+ necessary. */
+
+static inline tree
+mark_operand_necessary (tree op)
+{
+ tree stmt;
+
+ gcc_assert (op);
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return NULL;
+
+ stmt = SSA_NAME_DEF_STMT (op);
+ gcc_assert (stmt);
+
+ if (NECESSARY (stmt)
+ || IS_EMPTY_STMT (stmt))
+ return NULL;
+
+ NECESSARY (stmt) = 1;
+ return stmt;
+}
+
+/* Because we don't follow exactly the standard PRE algorithm, and decide not
+ to insert PHI nodes sometimes, and because value numbering of casts isn't
+ perfect, we sometimes end up inserting dead code. This simple DCE-like
+ pass removes any insertions we made that weren't actually used. */
+
+static void
+remove_dead_inserted_code (void)
+{
+ VEC(tree,heap) *worklist = NULL;
+ int i;
+ tree t;
+
+ worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
+ for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
+ {
+ if (NECESSARY (t))
+ VEC_quick_push (tree, worklist, t);
+ }
+ while (VEC_length (tree, worklist) > 0)
+ {
+ t = VEC_pop (tree, worklist);
+
+ /* PHI nodes are somewhat special in that each PHI alternative has
+ data and control dependencies. All the statements feeding the
+ PHI node's arguments are always necessary. */
+ if (TREE_CODE (t) == PHI_NODE)
+ {
+ int k;
+
+ 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)
+ {
+ arg = mark_operand_necessary (arg);
+ if (arg)
+ VEC_quick_push (tree, worklist, arg);
+ }
+ }
+ }
+ else
+ {
+ /* Propagate through the operands. Examine all the USE, VUSE and
+ V_MAY_DEF 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
+ represent potential definitions that may reach this
+ statement (V_MAY_DEF operands allow us to follow def-def
+ links). */
+
+ FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
+ {
+ tree n = mark_operand_necessary (use);
+ if (n)
+ VEC_safe_push (tree, heap, worklist, n);
+ }
+ }
+ }
+
+ for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
+ {
+ if (!NECESSARY (t))
+ {
+ block_stmt_iterator bsi;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Removing unnecessary insertion:");
+ print_generic_stmt (dump_file, t, 0);
+ }
+
+ if (TREE_CODE (t) == PHI_NODE)
+ {
+ remove_phi_node (t, NULL);
+ }
+ else
+ {
+ bsi = bsi_for_stmt (t);
+ bsi_remove (&bsi, true);
+ release_defs (t);
+ }
+ }
+ }
+ VEC_free (tree, heap, worklist);
+}
/* Initialize data structures used by PRE. */
static void
-init_pre (void)
+init_pre (bool do_fre)
{
- size_t tsize;
basic_block bb;
+
+ in_fre = do_fre;
+
+ inserted_exprs = NULL;
+ need_creation = NULL;
+ pretemp = NULL_TREE;
+ storetemp = NULL_TREE;
+ mergephitemp = NULL_TREE;
+ prephitemp = NULL_TREE;
- connect_infinite_loops_to_exit ();
vn_init ();
+ if (!do_fre)
+ current_loops = 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
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 (ENTRY_BLOCK_PTR->succ->dest->pred->pred_next)
- if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_ABNORMAL))
- split_edge (ENTRY_BLOCK_PTR->succ);
+ 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));
FOR_ALL_BB (bb)
bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
+ bitmap_obstack_initialize (&grand_bitmap_obstack);
phi_translate_table = htab_create (511, expr_pred_trans_hash,
expr_pred_trans_eq, free);
value_set_pool = create_alloc_pool ("Value sets",
sizeof (struct value_set_node), 30);
calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
- tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE, NULL_TREE));
- binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
- tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
- unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
- tsize = tree_size (build (COMPONENT_REF, void_type_node, NULL_TREE,
- NULL_TREE, NULL_TREE));
- reference_node_pool = create_alloc_pool ("Reference tree nodes", tsize, 30);
+ binary_node_pool = create_alloc_pool ("Binary tree nodes",
+ 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),
+ 30);
+ modify_expr_template = NULL;
+
FOR_ALL_BB (bb)
{
EXP_GEN (bb) = set_new (true);
AVAIL_OUT (bb) = bitmap_set_new ();
}
- need_eh_cleanup = BITMAP_XMALLOC ();
+ need_eh_cleanup = BITMAP_ALLOC (NULL);
}
/* Deallocate data structures used by PRE. */
static void
-fini_pre (void)
+fini_pre (bool do_fre)
{
basic_block bb;
+ unsigned int i;
+ VEC_free (tree, heap, inserted_exprs);
+ VEC_free (tree, heap, need_creation);
+ bitmap_obstack_release (&grand_bitmap_obstack);
free_alloc_pool (value_set_pool);
free_alloc_pool (bitmap_set_pool);
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);
remove_fake_exit_edges ();
free_dominance_info (CDI_POST_DOMINATORS);
vn_delete ();
- if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
+ if (!bitmap_empty_p (need_eh_cleanup))
{
tree_purge_all_dead_eh_edges (need_eh_cleanup);
cleanup_tree_cfg ();
}
- BITMAP_XFREE (need_eh_cleanup);
-}
+ BITMAP_FREE (need_eh_cleanup);
+ /* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
+ future we will want them to be persistent though. */
+ for (i = 0; i < num_ssa_names; i++)
+ {
+ tree name = ssa_name (i);
+
+ if (!name)
+ continue;
+
+ if (SSA_NAME_VALUE (name)
+ && 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;
+ }
+}
/* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
only wants to do full redundancy elimination. */
static void
execute_pre (bool do_fre)
{
- init_pre ();
+ init_pre (do_fre);
+
+ if (!do_fre)
+ insert_fake_stores ();
- /* Collect and value number expressions computed in each basic
- block. */
- compute_avail (ENTRY_BLOCK_PTR);
+ /* Collect and value number expressions computed in each basic block. */
+ compute_avail ();
if (dump_file && (dump_flags & TDF_DETAILS))
{
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, "New PHIs:%d\n", pre_stats.phis);
- fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
+ fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
+ 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 ();
+
+ if (!do_fre)
+ {
+ remove_dead_inserted_code ();
+ realify_fake_stores ();
}
- fini_pre ();
-}
+ fini_pre (do_fre);
+}
/* Gate and execute functions for PRE. */
-static void
+static unsigned int
do_pre (void)
{
execute_pre (false);
+ return 0;
}
static bool
NULL, /* next */
0, /* static_pass_number */
TV_TREE_PRE, /* tv_id */
- PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
+ PROP_no_crit_edges | PROP_cfg
+ | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+ TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect
+ | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
};
/* Gate and execute functions for FRE. */
-static void
-do_fre (void)
+static unsigned int
+execute_fre (void)
{
execute_pre (true);
+ return 0;
}
static bool
{
"fre", /* name */
gate_fre, /* gate */
- do_fre, /* execute */
+ execute_fre, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
TV_TREE_FRE, /* tv_id */
- PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+ TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
};
+
OSDN Git Service
