/* Reassociation for trees.
- Copyright (C) 2005, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org>
This file is part of GCC.
#include "tree-dump.h"
#include "timevar.h"
#include "tree-iterator.h"
+#include "real.h"
#include "tree-pass.h"
#include "alloc-pool.h"
#include "vec.h"
mergetmp2 = d + e
and put mergetmp2 on the merge worklist.
-
+
so merge worklist = {mergetmp, c, mergetmp2}
-
+
Continue building binary ops of these operations until you have only
one operation left on the worklist.
-
+
So we have
-
+
build binary op
mergetmp3 = mergetmp + c
-
+
worklist = {mergetmp2, mergetmp3}
-
+
mergetmp4 = mergetmp2 + mergetmp3
-
+
worklist = {mergetmp4}
-
+
because we have one operation left, we can now just set the original
statement equal to the result of that operation.
-
+
This will at least expose a + b and d + e to redundancy elimination
as binary operations.
-
+
For extra points, you can reuse the old statements to build the
mergetmps, since you shouldn't run out.
So why don't we do this?
-
+
Because it's expensive, and rarely will help. Most trees we are
reassociating have 3 or less ops. If they have 2 ops, they already
will be written into a nice single binary op. If you have 3 ops, a
mergetmp = op1 + op2
newstmt = mergetmp + op3
-
+
instead of
mergetmp = op2 + op3
newstmt = mergetmp + op1
-
+
If all three are of the same rank, you can't expose them all in a
single binary operator anyway, so the above is *still* the best you
can do.
-
+
Thus, this is what we do. When we have three ops left, we check to see
what order to put them in, and call it a day. As a nod to vector sum
reduction, we check if any of the ops are really a phi node that is a
find_operand_rank (tree e)
{
void **slot = pointer_map_contains (operand_rank, e);
- return slot ? (long) *slot : -1;
+ return slot ? (long) (intptr_t) *slot : -1;
}
/* Insert {E,RANK} into the operand rank hashtable. */
gcc_assert (rank > 0);
slot = pointer_map_insert (operand_rank, e);
gcc_assert (!*slot);
- *slot = (void *) rank;
+ *slot = (void *) (intptr_t) rank;
}
/* Given an expression E, return the rank of the expression. */
{
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
- add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op),
+ add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op),
integer_zero_node));
*all_done = true;
}
}
VEC_ordered_remove (operand_entry_t, *ops, i);
- add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op),
+ add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op),
integer_zero_node));
VEC_ordered_remove (operand_entry_t, *ops, currindex);
reassociate_stats.ops_eliminated ++;
oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
TYPE_PRECISION (TREE_TYPE (oe->op)));
- reassociate_stats.ops_eliminated
+ reassociate_stats.ops_eliminated
+= VEC_length (operand_entry_t, *ops) - 1;
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found & 0, removing all other ops\n");
- reassociate_stats.ops_eliminated
+ reassociate_stats.ops_eliminated
+= VEC_length (operand_entry_t, *ops) - 1;
-
+
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
VEC_safe_push (operand_entry_t, heap, *ops, oelast);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found | -1, removing all other ops\n");
- reassociate_stats.ops_eliminated
+ reassociate_stats.ops_eliminated
+= VEC_length (operand_entry_t, *ops) - 1;
-
+
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
VEC_safe_push (operand_entry_t, heap, *ops, oelast);
return;
}
- }
+ }
else if (integer_zerop (oelast->op))
{
if (VEC_length (operand_entry_t, *ops) != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found * 0, removing all other ops\n");
-
- reassociate_stats.ops_eliminated
+
+ reassociate_stats.ops_eliminated
+= VEC_length (operand_entry_t, *ops) - 1;
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
if ((!op1def || gimple_nop_p (op1def))
&& (!op2def || gimple_nop_p (op2def)))
{
- gsi = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR));
+ gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
}
else if ((!op1def || gimple_nop_p (op1def))
{
if (gimple_code (op2def) == GIMPLE_PHI)
{
- gsi = gsi_start_bb (gimple_bb (op2def));
+ gsi = gsi_after_labels (gimple_bb (op2def));
gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
}
else
{
if (gimple_code (op1def) == GIMPLE_PHI)
{
- gsi = gsi_start_bb (gimple_bb (op1def));
+ gsi = gsi_after_labels (gimple_bb (op1def));
gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
}
else
We do this top down because we don't know whether the subtract is
part of a possible chain of reassociation except at the top.
-
+
IE given
d = f + g
c = a + e
b = c - d
q = b - r
k = t - q
-
+
we want to break up k = t - q, but we won't until we've transformed q
= b - r, which won't be broken up until we transform b = c - d.
NULL, /* next */
0, /* static_pass_number */
TV_TREE_REASSOC, /* tv_id */
- PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ PROP_cfg | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */