/* TODO:
- 1. Implement load value numbering.
- 2. Speed up insert_aux so that we can use it all the time. It
- spends most of it's time in quadratic value replacement.
- 3. Avail sets can be shared by making an avail_find_leader that
+ 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.
- 4. Load motion can be performed by value numbering the loads the
+ 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.
- 5. Strength reduction can be performed by anticipating expressions
+ 3. Strength reduction can be performed by anticipating expressions
we can repair later on.
- 6. Our canonicalization of expressions during lookups don't take
+ 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
/* Representation of sets:
- Sets are represented as doubly linked lists kept in topological
+ There are currently two types of sets used, hopefully to be unified soon.
+ The AVAIL sets do not need to be sorted in any particular order,
+ and thus, are simply represented as two bitmaps, one that keeps
+ track of values present in the set, and one that keeps track of
+ expressions present in the set.
+
+ The other sets are represented as doubly linked lists kept in topological
order, with an optional supporting bitmap of values present in the
set. The sets represent values, and the elements can be values or
expressions. The elements can appear in different sets, but each
} *value_set_t;
-/* All of the following sets, except for TMP_GEN, are indexed.
- TMP_GEN is only ever iterated over, we never check what values
- exist in it. */
+/* An unordered bitmap set. One bitmap tracks values, the other,
+ expressions. */
+typedef struct bitmap_set
+{
+ bitmap expressions;
+ bitmap values;
+} *bitmap_set_t;
+
+/* Sets that we need to keep track of. */
typedef struct bb_value_sets
{
/* The EXP_GEN set, which represents expressions/values generated in
/* The PHI_GEN set, which represents PHI results generated in a
basic block. */
- value_set_t phi_gen;
+ bitmap_set_t phi_gen;
- /* The TMP_GEN set, which represents results/temporaries genererated
+ /* The TMP_GEN set, which represents results/temporaries generated
in a basic block. IE the LHS of an expression. */
- value_set_t tmp_gen;
+ bitmap_set_t tmp_gen;
/* The AVAIL_OUT set, which represents which values are available in
a given basic block. */
- value_set_t avail_out;
+ bitmap_set_t avail_out;
/* The ANTIC_IN set, which represents which values are anticiptable
in a given basic block. */
/* The NEW_SETS set, which is used during insertion to augment the
AVAIL_OUT set of blocks with the new insertions performed during
the current iteration. */
- value_set_t new_sets;
+ bitmap_set_t new_sets;
} *bb_value_sets_t;
#define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
int phis;
} pre_stats;
+
+static tree bitmap_find_leader (bitmap_set_t, tree);
static tree find_leader (value_set_t, tree);
static void value_insert_into_set (value_set_t, tree);
+static void bitmap_value_insert_into_set (bitmap_set_t, tree);
+static void bitmap_value_replace_in_set (bitmap_set_t, tree);
static void insert_into_set (value_set_t, tree);
+static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
+static bool bitmap_set_contains_value (bitmap_set_t, tree);
+static bitmap_set_t bitmap_set_new (void);
static value_set_t set_new (bool);
static bool is_undefined_value (tree);
static tree create_expression_by_pieces (basic_block, tree, tree);
+
/* We can add and remove elements and entries to and from sets
and hash tables, so we use alloc pools for them. */
static alloc_pool value_set_pool;
+static alloc_pool bitmap_set_pool;
static alloc_pool value_set_node_pool;
static alloc_pool binary_node_pool;
static alloc_pool unary_node_pool;
+static alloc_pool reference_node_pool;
+static struct obstack grand_bitmap_obstack;
+/* Set of blocks with statements that have had its EH information
+ cleaned up. */
+static bitmap need_eh_cleanup;
/* The phi_translate_table caches phi translations for a given
expression and predecessor. */
typedef struct expr_pred_trans_d
{
- /* The expression. */
+ /* The expression. */
tree e;
/* The predecessor block along which we translated the expression. */
/* 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 ();
+ set->values = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
bitmap_clear (set->values);
}
}
+/* Create a new bitmap set and return it. */
+
+static bitmap_set_t
+bitmap_set_new (void)
+{
+ bitmap_set_t ret = pool_alloc (bitmap_set_pool);
+ ret->expressions = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
+ ret->values = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
+ bitmap_clear (ret->expressions);
+ bitmap_clear (ret->values);
+ return ret;
+}
+
/* Create a new set. */
static value_set_t
return ret;
}
+/* Insert an expression EXPR into a bitmapped set. */
+
+static void
+bitmap_insert_into_set (bitmap_set_t set, tree expr)
+{
+ tree val;
+ /* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
+ gcc_assert (TREE_CODE (expr) == SSA_NAME);
+ val = get_value_handle (expr);
+
+ 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));
+ }
+}
/* 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
}
}
+/* Copy a bitmapped set ORIG, into bitmapped set DEST. */
+
+static void
+bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
+{
+ bitmap_copy (dest->expressions, orig->expressions);
+ bitmap_copy (dest->values, orig->values);
+}
+
/* Copy the set ORIG to the set DEST. */
static void
return value_exists_in_set_bitmap (set, val);
}
-/* Replace the leader for the value LOOKFOR in SET with EXPR. */
-
-static void
-set_replace_value (value_set_t set, tree lookfor, tree expr)
+/* Return true if bitmapped set SET contains the expression EXPR. */
+static bool
+bitmap_set_contains (bitmap_set_t set, tree expr)
{
- value_set_node_t node = set->head;
-
- /* The lookup is probably more expensive than walking the linked
- list when we have only a small number of nodes. */
- if (!set_contains_value (set, lookfor))
- return;
+ /* All constants are in every set. */
+ if (is_gimple_min_invariant (get_value_handle (expr)))
+ return true;
- for (node = set->head;
- node;
- node = node->next)
- {
- if (get_value_handle (node->expr) == lookfor)
- {
- node->expr = expr;
- return;
- }
- }
+ /* XXX: Bitmapped sets only contain SSA_NAME's for now. */
+ if (TREE_CODE (expr) != SSA_NAME)
+ return false;
+ return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
}
-/* Return true if the set contains expression (not value) EXPR. */
+
+/* Return true if bitmapped set SET contains the value VAL. */
static bool
-set_contains (value_set_t set, tree expr)
+bitmap_set_contains_value (bitmap_set_t set, tree val)
{
+ if (is_gimple_min_invariant (val))
+ return true;
+ return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
+}
+
+/* Replace an instance of value LOOKFOR with expression EXPR in SET. */
+
+static void
+bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
+{
+ value_set_t exprset;
value_set_node_t node;
-
- for (node = set->head;
- node;
- node = node->next)
+ if (is_gimple_min_invariant (lookfor))
+ 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
+ has the value LOOKFOR, we walk the reverse mapping that tells us
+ what expressions have a given value, and see if any of those
+ expressions are in our set. For large testcases, this is about
+ 5-10x faster than walking the bitmap. If this is somehow a
+ significant lose for some cases, we can choose which set to walk
+ based on the set size. */
+ exprset = VALUE_HANDLE_EXPR_SET (lookfor);
+ for (node = exprset->head; node; node = node->next)
{
- if (operand_equal_p (node->expr, expr, 0))
- return true;
+ if (TREE_CODE (node->expr) == SSA_NAME)
+ {
+ if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
+ {
+ bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
+ bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
+ return;
+ }
+ }
}
- return false;
}
-/* Subtract set B from set A, and return the new set. */
+/* Subtract bitmapped set B from value set A, and return the new set. */
static value_set_t
-set_subtract (value_set_t a, value_set_t b, bool indexed)
+bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
+ bool indexed)
{
value_set_t ret = set_new (indexed);
value_set_node_t node;
node;
node = node->next)
{
- if (!set_contains (b, node->expr))
+ if (!bitmap_set_contains (b, node->expr))
insert_into_set (ret, node->expr);
}
return ret;
}
-/* Return true if two sets are equal. */
+/* Return true if two sets are equal. */
static bool
set_equal (value_set_t a, value_set_t b)
return true;
}
-/* Replace the value for EXPR in SET with EXPR. */
+/* Replace an instance of EXPR's VALUE with EXPR in SET. */
+
static void
-value_replace_in_set (value_set_t set, tree expr)
+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 (set->length == 0)
+/* Insert EXPR into SET if EXPR's value is not already present in
+ SET. */
+
+static void
+bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
+{
+ tree val = get_value_handle (expr);
+
+ if (is_gimple_min_invariant (val))
return;
- set_replace_value (set, val, expr);
+ if (!bitmap_set_contains_value (set, val))
+ bitmap_insert_into_set (set, expr);
}
/* Insert the value for EXPR into SET, if it doesn't exist already. */
}
+/* Print out SET to OUTFILE. */
+
+static void
+bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
+ const char *setname, int blockindex)
+{
+ fprintf (outfile, "%s[%d] := { ", setname, blockindex);
+ if (set)
+ {
+ int i;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
+ {
+ 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, " }\n");
+}
/* Print out the value_set SET to OUTFILE. */
static void
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 ();
+ 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 PHI_ARG_DEF (phi, i);
}
}
- break;
+ return expr;
+
+ default:
+ gcc_unreachable ();
}
- return expr;
}
static void
found. */
static tree
+bitmap_find_leader (bitmap_set_t set, tree val)
+{
+ if (val == NULL)
+ return NULL;
+
+ if (is_gimple_min_invariant (val))
+ return val;
+ if (bitmap_set_contains_value (set, val))
+ {
+ /* Rather than walk the entire bitmap of expressions, and see
+ whether any of them has the value we are looking for, we look
+ at the reverse mapping, which tells us the set of expressions
+ that have a given value (IE value->expressions with that
+ value) and see if any of those expressions are in our set.
+ The number of expressions per value is usually significantly
+ less than the number of expressions in the set. In fact, for
+ large testcases, doing it this way is roughly 5-10x faster
+ than walking the bitmap.
+ If this is somehow a significant lose for some cases, we can
+ choose which set to walk based on which set is smaller. */
+ value_set_t exprset;
+ value_set_node_t node;
+ exprset = VALUE_HANDLE_EXPR_SET (val);
+ for (node = exprset->head; node; node = node->next)
+ {
+ if (TREE_CODE (node->expr) == SSA_NAME)
+ {
+ if (bitmap_bit_p (set->expressions,
+ SSA_NAME_VERSION (node->expr)))
+ return node->expr;
+ }
+ }
+ }
+ return NULL;
+}
+
+
+/* Find the leader for a value (i.e., the name representing that
+ value) in a given set, and return it. Return NULL if no leader is
+ found. */
+
+static tree
find_leader (value_set_t set, tree val)
{
value_set_node_t node;
{
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
}
}
+DEF_VEC_MALLOC_P (basic_block);
+
/* Compute the ANTIC set for BLOCK.
ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
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;
- }
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, block->preds)
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ block->flags |= BB_VISITED;
+ break;
+ }
}
if (block->flags & BB_VISITED)
{
/* If the block has no successors, ANTIC_OUT is empty, because it is
the exit block. */
- if (block->succ == NULL);
+ 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 */
- S = set_subtract (ANTIC_OUT, TMP_GEN (block), false);
+ /* 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) = set_subtract (EXP_GEN (block),TMP_GEN (block), true);
+ 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_ALL_BB (bb)
{
ANTIC_IN (bb) = set_new (true);
- if (bb->flags & BB_VISITED)
- abort ();
+ gcc_assert (!(bb->flags & BB_VISITED));
}
while (changed)
find_or_generate_expression (basic_block block, tree expr, tree stmts)
{
tree genop;
- genop = find_leader (AVAIL_OUT (block), expr);
+ 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 = find_leader (NEW_SETS (block), expr);
+ 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)
{
genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
- if (TREE_CODE_CLASS (TREE_CODE (genop)) != '1'
- && TREE_CODE_CLASS (TREE_CODE (genop)) != '2')
- 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;
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
{
- case '2':
+ case tcc_binary:
{
tree_stmt_iterator tsi;
tree genop1, genop2;
pre_stats.insertions++;
break;
}
- case '1':
+ case tcc_unary:
{
tree_stmt_iterator tsi;
tree genop1;
break;
}
default:
- abort ();
+ gcc_unreachable ();
}
v = get_value_handle (expr);
vn_add (name, v, NULL);
- insert_into_set (NEW_SETS (block), name);
- value_insert_into_set (AVAIL_OUT (block), name);
+ bitmap_insert_into_set (NEW_SETS (block), name);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), name);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Inserted ");
if (block)
{
- value_set_node_t e;
basic_block dom;
dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
{
- e = NEW_SETS (dom)->head;
- while (e)
+ int i;
+ bitmap_iterator bi;
+
+ bitmap_set_t newset = NEW_SETS (dom);
+ EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
{
- insert_into_set (NEW_SETS (block), e->expr);
- value_replace_in_set (AVAIL_OUT (block), e->expr);
- e = e->next;
+ 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 (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;
edge pred;
basic_block bprime;
tree eprime;
+ edge_iterator ei;
val = get_value_handle (node->expr);
- if (set_contains_value (PHI_GEN (block), val))
+ if (bitmap_set_contains_value (PHI_GEN (block), val))
continue;
- if (set_contains_value (AVAIL_OUT (dom), val))
+ if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found fully redundant value\n");
continue;
}
-
+
avail = 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;
+
+ /* This can happen in the very weird case
+ that our fake infinite loop edges have caused a
+ critical edge to appear. */
+ if (EDGE_CRITICAL_P (pred))
+ {
+ cant_insert = true;
+ break;
+ }
bprime = pred->src;
eprime = phi_translate (node->expr,
ANTIC_IN (block),
}
vprime = get_value_handle (eprime);
- if (!vprime)
- abort ();
- edoubleprime = find_leader (AVAIL_OUT (bprime),
- vprime);
+ gcc_assert (vprime);
+ edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
+ vprime);
if (edoubleprime == NULL)
{
avail[bprime->index] = eprime;
first_s = edoubleprime;
else if (first_s != edoubleprime)
all_same = false;
- if (first_s != edoubleprime
- && operand_equal_p (first_s, edoubleprime, 0))
- abort ();
+ gcc_assert (first_s == edoubleprime
+ || !operand_equal_p
+ (first_s, edoubleprime, 0));
}
}
/* 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 type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
tree temp;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\n");
}
- /* Make the necessary insertions. */
- for (pred = block->pred;
- pred;
- pred = pred->pred_next)
+ /* 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 (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2'
- || TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
+ if (BINARY_CLASS_P (eprime)
+ || UNARY_CLASS_P (eprime))
{
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);
PHI_RESULT (temp));
else
#endif
- value_replace_in_set (AVAIL_OUT (block),
- PHI_RESULT (temp));
- for (pred = block->pred;
- pred;
- pred = pred->pred_next)
+ bitmap_value_replace_in_set (AVAIL_OUT (block),
+ PHI_RESULT (temp));
+ FOR_EACH_EDGE (pred, ei, block->preds)
{
add_phi_arg (&temp, avail[pred->src->index],
pred);
}
pre_stats.phis++;
new_stuff = true;
- insert_into_set (NEW_SETS (block),
- PHI_RESULT (temp));
- insert_into_set (PHI_GEN (block),
- PHI_RESULT (temp));
+ bitmap_insert_into_set (NEW_SETS (block),
+ PHI_RESULT (temp));
+ bitmap_insert_into_set (PHI_GEN (block),
+ PHI_RESULT (temp));
}
free (avail);
bool new_stuff = true;
basic_block bb;
int num_iterations = 0;
-
+
FOR_ALL_BB (bb)
- NEW_SETS (bb) = set_new (true);
+ NEW_SETS (bb) = bitmap_set_new ();
while (new_stuff)
{
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);
}
any). They are used when computing the hash value for EXPR. */
static inline void
-add_to_sets (tree var, tree expr, vuse_optype vuses, value_set_t s1,
- value_set_t s2)
+add_to_sets (tree var, tree expr, vuse_optype vuses, bitmap_set_t s1,
+ bitmap_set_t s2)
{
tree val = vn_lookup_or_add (expr, vuses);
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, vuses);
+ vn_add (var, val, NULL);
- insert_into_set (s1, var);
- value_insert_into_set (s2, var);
+ 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
- expresion with the same structure as EXPR but with its operands
+ 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.
enum tree_code code = TREE_CODE (expr);
tree vexpr;
-#if defined ENABLE_CHECKING
- if (TREE_CODE_CLASS (code) != '1'
- && TREE_CODE_CLASS (code) != '2')
- 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) == tcc_reference)
+ vexpr = pool_alloc (reference_node_pool);
else
vexpr = pool_alloc (binary_node_pool);
for (i = 0; i < TREE_CODE_LENGTH (code); i++)
{
tree op = TREE_OPERAND (expr, i);
- tree val = vn_lookup_or_add (op, vuses);
- if (!is_undefined_value (op))
- value_insert_into_set (EXP_GEN (block), op);
- TREE_OPERAND (vexpr, i) = val;
+ if (op != NULL)
+ {
+ tree val = vn_lookup_or_add (op, vuses);
+ if (!is_undefined_value (op))
+ 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;
tree val;
tree def = default_def (param);
val = vn_lookup_or_add (def, NULL);
- insert_into_set (TMP_GEN (block), def);
- value_insert_into_set (AVAIL_OUT (block), def);
+ bitmap_insert_into_set (TMP_GEN (block), def);
+ bitmap_value_insert_into_set (AVAIL_OUT (block), def);
}
}
}
its immediate dominator. */
dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
- set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
+ bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
/* Generate values for PHI nodes. */
for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
- add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
- PHI_GEN (block), AVAIL_OUT (block));
+ /* We have no need for virtual phis, as they don't represent
+ actual computations. */
+ if (is_gimple_reg (PHI_RESULT (phi)))
+ add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
+ PHI_GEN (block), AVAIL_OUT (block));
/* Now compute value numbers and populate value sets with all
the expressions computed in BLOCK. */
vuse_optype vuses = STMT_VUSE_OPS (stmt);
STRIP_USELESS_TYPE_CONVERSION (rhs);
-
- if (TREE_CODE_CLASS (TREE_CODE (rhs)) == '1'
- || TREE_CODE_CLASS (TREE_CODE (rhs)) == '2')
- {
- /* For binary and unary 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;
- }
- else if (TREE_CODE (rhs) == SSA_NAME
- || is_gimple_min_invariant (rhs))
+ if (TREE_CODE (rhs) == SSA_NAME
+ || is_gimple_min_invariant (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. */
+ 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),
AVAIL_OUT (block));
-
+
if (TREE_CODE (rhs) == SSA_NAME
&& !is_undefined_value (rhs))
value_insert_into_set (EXP_GEN (block), rhs);
continue;
+ }
+ else if (UNARY_CLASS_P (rhs) || BINARY_CLASS_P (rhs)
+ || 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;
}
}
tree lhs = TREE_OPERAND (stmt, 0);
tree *rhs_p = &TREE_OPERAND (stmt, 1);
tree sprime;
- vuse_optype vuses = STMT_VUSE_OPS (stmt);
- sprime = find_leader (AVAIL_OUT (b), vn_lookup (lhs, vuses));
+ sprime = bitmap_find_leader (AVAIL_OUT (b),
+ vn_lookup (lhs, NULL));
if (sprime
&& sprime != lhs
&& (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))
{
pre_stats.eliminations++;
propagate_tree_value (rhs_p, sprime);
modify_stmt (stmt);
+
+ /* If we removed EH side effects from the statement, clean
+ its EH information. */
+ if (maybe_clean_eh_stmt (stmt))
+ {
+ bitmap_set_bit (need_eh_cleanup,
+ bb_for_stmt (stmt)->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Removed EH side effects.\n");
+ }
}
}
}
static void
init_pre (void)
{
- size_t tsize;
basic_block bb;
+ connect_infinite_loops_to_exit ();
vn_init ();
memset (&pre_stats, 0, sizeof (pre_stats));
+
+ /* If block 0 has more than one predecessor, it means that its PHI
+ nodes will have arguments coming from block -1. This creates
+ problems for several places in PRE that keep local arrays indexed
+ by block number. To prevent this, we split the edge coming from
+ ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
+ different than -1 we wouldn't have to hack this. tree-ssa-dce.c
+ needs a similar change). */
+ if (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));
+ gcc_obstack_init (&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), 30);
+ bitmap_set_pool = create_alloc_pool ("Bitmap sets",
+ sizeof (struct bitmap_set), 30);
value_set_node_pool = create_alloc_pool ("Value set nodes",
sizeof (struct value_set_node), 30);
calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
- 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);
-
+ 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);
- PHI_GEN (bb) = set_new (true);
- TMP_GEN (bb) = set_new (false);
- AVAIL_OUT (bb) = set_new (true);
+ PHI_GEN (bb) = bitmap_set_new ();
+ TMP_GEN (bb) = bitmap_set_new ();
+ AVAIL_OUT (bb) = bitmap_set_new ();
}
+
+ need_eh_cleanup = BITMAP_XMALLOC ();
}
fini_pre (void)
{
basic_block bb;
+ unsigned int i;
+ bsi_commit_edge_inserts (NULL);
+
+ obstack_free (&grand_bitmap_obstack, NULL);
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);
htab_delete (phi_translate_table);
-
+ remove_fake_exit_edges ();
+
FOR_ALL_BB (bb)
{
free (bb->aux);
bb->aux = NULL;
}
+
free_dominance_info (CDI_POST_DOMINATORS);
vn_delete ();
+
+ if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
+ {
+ tree_purge_all_dead_eh_edges (need_eh_cleanup);
+ cleanup_tree_cfg ();
+ }
+
+ BITMAP_XFREE (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;
+ }
}
FOR_ALL_BB (bb)
{
print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
- print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
- print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
+ bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen",
+ bb->index);
+ bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
+ bb->index);
}
}
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_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
};
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
