/* 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
{
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
{
stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1));
gsirhs1 = gsi_for_stmt (stmt2);
- propagate_defs_into_debug_stmts (stmt2, gimple_bb (stmt), &gsinow);
gsi_move_before (&gsirhs1, &gsinow);
gsi_prev (&gsinow);
stmt1 = stmt2;
gsinow = gsi_for_stmt (stmt);
gsirhs = gsi_for_stmt (binrhs);
- propagate_defs_into_debug_stmts (binrhs, gimple_bb (stmt), &gsinow);
gsi_move_before (&gsirhs, &gsinow);
gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs));
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.
OSDN Git Service
