/* 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>
#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:
a new value every time we see a statement with a vuse.
3. 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.
+ 4. We can do back-substitution or smarter value numbering to catch
+ commutative expressions split up over multiple statements.
*/
/* For ease of terminology, "expression node" in the below refers to
/* An unordered bitmap set. One bitmap tracks values, the other,
- expressions. */
+ expressions. */
typedef struct bitmap_set
{
bitmap expressions;
/* The number of new PHI nodes added by PRE. */
int phis;
+
+ /* The number of values found constant. */
+ int constified;
+
} pre_stats;
static alloc_pool binary_node_pool;
static alloc_pool unary_node_pool;
static alloc_pool reference_node_pool;
+static bitmap_obstack grand_bitmap_obstack;
/* 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. */
return false;
/* If they are for the same basic block, determine if the
- expressions are equal. */
+ expressions are equal. */
if (expressions_equal_p (ve1->e, ve2->e))
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. */
+ found, NULL otherwise. */
static inline tree
phi_trans_lookup (tree e, basic_block pred)
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));
}
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);
+ ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
+ ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
return ret;
}
{
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. */
{
value_set_node_t newnode = 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
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
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");
}
if (expr == NULL)
return NULL;
- /* Phi translations of a given expression don't change, */
+ if (is_gimple_min_invariant (expr))
+ return expr;
+
+ /* Phi translations of a given expression don't change. */
phitrans = phi_trans_lookup (expr, pred);
if (phitrans)
return phitrans;
-
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
- case '2':
+ case tcc_reference:
+ /* XXX: Until we have PRE of loads working, none will be ANTIC. */
+ return NULL;
+
+ case tcc_binary:
{
tree oldop1 = TREE_OPERAND (expr, 0);
tree oldop2 = TREE_OPERAND (expr, 1);
phi_trans_add (oldexpr, newexpr, pred);
}
}
- 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;
phi_trans_add (oldexpr, newexpr, pred);
}
}
- 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;
}
static void
{
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
- case '2':
+ case tcc_binary:
{
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':
- {
- return false;
- }
- case 'x':
- {
- if (TREE_CODE (expr) == SSA_NAME)
- return true;
- abort ();
- }
- case 'c':
- abort ();
- }
- return false;
+
+ case tcc_reference:
+ /* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
+ return false;
+
+ case tcc_exceptional:
+ gcc_assert (TREE_CODE (expr) == SSA_NAME);
+ return true;
+
+ default:
+ /* No other cases should be encountered. */
+ gcc_unreachable ();
+ }
}
/* Clean the set of expressions that are no longer valid in SET. This
}
}
-/* 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
+DEF_VEC_MALLOC_P (basic_block);
+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 (EDGE_COUNT (block->succs) == 1)
{
- phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
- block, block->succ->dest);
+ phi_translate_set (ANTIC_OUT, ANTIC_IN(EDGE_SUCC (block, 0)->dest),
+ block, EDGE_SUCC (block, 0)->dest);
}
/* If we have multiple successors, we take the intersection of all of
them. */
else
{
- varray_type worklist;
+ VEC (basic_block) * 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, 2);
+ FOR_EACH_EDGE (e, ei, block->succs)
+ VEC_safe_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)
{
node = next;
}
}
- VARRAY_CLEAR (worklist);
+ VEC_free (basic_block, 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));
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_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);
- }
- FOR_ALL_BB (bb)
- {
- bb->flags &= ~BB_VISITED;
+ changed = compute_antic_aux (EXIT_BLOCK_PTR, false);
}
- if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
+
+ sbitmap_free (has_abnormal_preds);
+
+ if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
}
-
+static VEC(tree_on_heap) *inserted_exprs;
/* Find a leader for an expression, or generate one using
create_expression_by_pieces if it's ANTIC but
complex.
static tree
find_or_generate_expression (basic_block block, tree expr, tree stmts)
{
- 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);
+ tree genop = bitmap_find_leader (AVAIL_OUT (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)
{
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 ();
+ gcc_assert (UNARY_CLASS_P (genop)
+ || BINARY_CLASS_P (genop)
+ || REFERENCE_CLASS_P (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,
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
- case '2':
+ case tcc_binary:
{
tree_stmt_iterator tsi;
tree genop1, genop2;
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 = fold (build (TREE_CODE (expr), TREE_TYPE (expr),
+ genop1, genop2));
newexpr = build (MODIFY_EXPR, TREE_TYPE (expr),
temp, newexpr);
+ NECESSARY (newexpr) = 0;
name = make_ssa_name (temp, newexpr);
TREE_OPERAND (newexpr, 0) = name;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
+ VEC_safe_push (tree_on_heap, inserted_exprs, newexpr);
pre_stats.insertions++;
break;
}
- case '1':
+ case tcc_unary:
{
tree_stmt_iterator tsi;
tree genop1;
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 = fold (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;
+ NECESSARY (newexpr) = 0;
tsi = tsi_last (stmts);
tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
+ VEC_safe_push (tree_on_heap, inserted_exprs, newexpr);
pre_stats.insertions++;
break;
}
default:
- abort ();
+ gcc_unreachable ();
}
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);
+
+ /* 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. */
+ bitmap_value_replace_in_set (NEW_SETS (block), name);
+ bitmap_value_replace_in_set (AVAIL_OUT (block), name);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Inserted ");
}
return name;
}
+
+/* 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;
+}
+
+/* Insert the to-be-made-available values of NODE for each predecessor, stored
+ in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
+ node, given the same value handle as NODE. The prefix of the phi node is
+ given with TMPNAME. Return true if we have inserted new stuff. */
+
+static bool
+insert_into_preds_of_block (basic_block block, value_set_node_t node,
+ tree *avail, const char *tmpname)
+{
+ 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, "\n");
+ }
+
+ /* Make sure we aren't creating an induction variable. */
+ if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
+ {
+ 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 (BINARY_CLASS_P (eprime)
+ || UNARY_CLASS_P (eprime))
+ {
+ 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. */
+ temp = create_tmp_var (type, tmpname);
+ add_referenced_tmp_var (temp);
+ temp = create_phi_node (temp, block);
+ NECESSARY (temp) = 0;
+ VEC_safe_push (tree_on_heap, inserted_exprs, temp);
+ FOR_EACH_EDGE (pred, ei, block->preds)
+ add_phi_arg (temp, avail[pred->src->index], pred);
+
+ vn_add (PHI_RESULT (temp), val, NULL);
+
+ /* 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 (EDGE_COUNT (block->preds) > 1)
{
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 (BINARY_CLASS_P (node->expr)
+ || UNARY_CLASS_P (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)
+ 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");
- }
-
- /* 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 (insert_into_preds_of_block (block, node, avail,
+ "prephitmp"))
+ 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 (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, NULL);
+ pre_stats.constified++;
+ }
+ }
}
-
free (avail);
}
}
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)));
+ && TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
}
if (var != expr)
vn_add (var, val, NULL);
- bitmap_insert_into_set (s1, var);
+ if (s1)
+ bitmap_insert_into_set (s1, var);
bitmap_value_insert_into_set (s2, var);
}
enum tree_code code = TREE_CODE (expr);
tree vexpr;
-#if defined ENABLE_CHECKING
- if (TREE_CODE_CLASS (code) != '1'
- && TREE_CODE_CLASS (code) != '2'
- && TREE_CODE_CLASS (code) != 'r')
- abort ();
-#endif
+ gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
+ || TREE_CODE_CLASS (code) == tcc_binary
+ || TREE_CODE_CLASS (code) == tcc_reference);
- if (TREE_CODE_CLASS (code) == '1')
+ if (TREE_CODE_CLASS (code) == tcc_unary)
vexpr = pool_alloc (unary_node_pool);
- else if (TREE_CODE_CLASS (code) == 'r')
+ else if (TREE_CODE_CLASS (code) == tcc_reference)
vexpr = pool_alloc (reference_node_pool);
else
vexpr = pool_alloc (binary_node_pool);
}
-/* 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
+/* Compute the AVAIL set for all basic blocks.
+
+ 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 val;
+ tree def = default_def (param);
+ val = 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)
+
+ /* Allocate the worklist. */
+ worklist = xmalloc (sizeof (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;
+ /* Pick a block from the worklist. */
+ block = worklist[--sp];
+
/* Initially, the set of available values in BLOCK is that of
its immediate dominator. */
dom = get_immediate_dominator (CDI_DOMINATORS, block);
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'
+ else if (UNARY_CLASS_P (rhs) || BINARY_CLASS_P (rhs)
|| TREE_CODE (rhs) == INDIRECT_REF)
{
/* For binary, unary, and reference expressions,
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));
+ add_to_sets (use, use, 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;
pre_stats.eliminations++;
propagate_tree_value (rhs_p, sprime);
modify_stmt (stmt);
}
}
+/* 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. and place it on the WORKLIST. */
+
+static inline void
+mark_operand_necessary (tree op, VEC(tree_on_heap) **worklist)
+{
+ tree stmt;
+ int ver;
+
+ gcc_assert (op);
+
+ ver = SSA_NAME_VERSION (op);
+
+ stmt = SSA_NAME_DEF_STMT (op);
+ gcc_assert (stmt);
+
+ if (NECESSARY (stmt)
+ || IS_EMPTY_STMT (stmt))
+ return;
+
+ NECESSARY (stmt) = 1;
+ VEC_safe_push (tree_on_heap, *worklist, 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_on_heap) *worklist = NULL;
+ int i;
+ tree t;
+
+ for (i = 0; VEC_iterate (tree_on_heap, inserted_exprs, i, t); i++)
+ {
+ if (NECESSARY (t))
+ VEC_safe_push (tree_on_heap, worklist, t);
+ }
+ while (VEC_length (tree_on_heap, worklist) > 0)
+ {
+ t = VEC_pop (tree_on_heap, worklist);
+ if (TREE_CODE (t) == PHI_NODE)
+ {
+ /* PHI nodes are somewhat special in that each PHI alternative has
+ data and control dependencies. All the statements feeding the
+ PHI node's arguments are always necessary. In aggressive mode,
+ we also consider the control dependent edges leading to the
+ predecessor block associated with each PHI alternative as
+ necessary. */
+ int k;
+ for (k = 0; k < PHI_NUM_ARGS (t); k++)
+ {
+ tree arg = PHI_ARG_DEF (t, k);
+ if (TREE_CODE (arg) == SSA_NAME)
+ mark_operand_necessary (arg, &worklist);
+ }
+ }
+ 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;
+
+ get_stmt_operands (t);
+
+ /* 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)
+ mark_operand_necessary (use, &worklist);
+ }
+ }
+ for (i = 0; VEC_iterate (tree_on_heap, 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);
+ }
+ }
+ }
+ VEC_free (tree_on_heap, worklist);
+}
/* Initialize data structures used by PRE. */
static void
-init_pre (void)
+init_pre (bool do_fre)
{
- size_t tsize;
basic_block bb;
- connect_infinite_loops_to_exit ();
+ inserted_exprs = NULL;
vn_init ();
+ if (!do_fre)
+ current_loops = loop_optimizer_init (dump_file);
+ 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 (EDGE_COUNT (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->preds) > 1)
+ if (!(EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->flags & EDGE_ABNORMAL))
+ split_edge (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
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);
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_on_heap, inserted_exprs);
+ 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_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, dump_file);
+ current_loops = NULL;
+ }
}
static void
execute_pre (bool do_fre)
{
- init_pre ();
+ init_pre (do_fre);
- /* 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))
{
/* 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, "Constified:%d\n", pre_stats.constified);
}
+
+ bsi_commit_edge_inserts ();
+ if (!do_fre)
+ remove_dead_inserted_code ();
+ fini_pre (do_fre);
- fini_pre ();
}
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 */
};
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 */
};