/* Reassociation for trees.
- Copyright (C) 2005, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
+ Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org>
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "ggc.h"
#include "tree.h"
#include "basic-block.h"
-#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "tree-inline.h"
#include "tree-flow.h"
#include "gimple.h"
#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"
{
VEC_free (operand_entry_t, heap, *ops);
*ops = NULL;
- add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op),
- integer_zero_node));
+ add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (last->op)));
*all_done = true;
}
else
static VEC(tree, heap) *plus_negates;
-/* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,
- look in OPS for a corresponding positive operation to cancel it
- out. If we find one, remove the other from OPS, replace
- OPS[CURRINDEX] with 0, and return true. Otherwise, return
- false. */
+/* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not
+ expression, look in OPS for a corresponding positive operation to cancel
+ it out. If we find one, remove the other from OPS, replace
+ OPS[CURRINDEX] with 0 or -1, respectively, and return true. Otherwise,
+ return false. */
static bool
eliminate_plus_minus_pair (enum tree_code opcode,
operand_entry_t curr)
{
tree negateop;
+ tree notop;
unsigned int i;
operand_entry_t oe;
return false;
negateop = get_unary_op (curr->op, NEGATE_EXPR);
- if (negateop == NULL_TREE)
+ notop = get_unary_op (curr->op, BIT_NOT_EXPR);
+ if (negateop == NULL_TREE && notop == NULL_TREE)
return false;
/* Any non-negated version will have a rank that is one less than
}
VEC_ordered_remove (operand_entry_t, *ops, i);
- add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op),
- integer_zero_node));
+ add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (oe->op)));
+ VEC_ordered_remove (operand_entry_t, *ops, currindex);
+ reassociate_stats.ops_eliminated ++;
+
+ return true;
+ }
+ else if (oe->op == notop)
+ {
+ tree op_type = TREE_TYPE (oe->op);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Equivalence: ");
+ print_generic_expr (dump_file, notop, 0);
+ fprintf (dump_file, " + ~");
+ print_generic_expr (dump_file, oe->op, 0);
+ fprintf (dump_file, " -> -1\n");
+ }
+
+ VEC_ordered_remove (operand_entry_t, *ops, i);
+ add_to_ops_vec (ops, build_int_cst_type (op_type, -1));
VEC_ordered_remove (operand_entry_t, *ops, currindex);
reassociate_stats.ops_eliminated ++;
/* CURR->OP is a negate expr in a plus expr: save it for later
inspection in repropagate_negates(). */
- VEC_safe_push (tree, heap, plus_negates, curr->op);
+ if (negateop != NULL_TREE)
+ VEC_safe_push (tree, heap, plus_negates, curr->op);
return false;
}
}
if (opcode == BIT_AND_EXPR)
- oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node);
+ oe->op = build_zero_cst (TREE_TYPE (oe->op));
else if (opcode == BIT_IOR_EXPR)
oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
TYPE_PRECISION (TREE_TYPE (oe->op)));
candidates = sbitmap_alloc (length);
sbitmap_zero (candidates);
nr_candidates = 0;
- for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe1); ++i)
+ FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe1)
{
enum tree_code dcode;
gimple oe1def;
linearize_expr_tree (&subops[i], oedef,
associative_tree_code (oecode), false);
- for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
+ FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1)
{
oecount c;
void **slot;
htab_delete (ctable);
/* Sort the counting table. */
- qsort (VEC_address (oecount, cvec), VEC_length (oecount, cvec),
- sizeof (oecount), oecount_cmp);
+ VEC_qsort (oecount, cvec, oecount_cmp);
if (dump_file && (dump_flags & TDF_DETAILS))
{
oecount *c;
fprintf (dump_file, "Candidates:\n");
- for (j = 0; VEC_iterate (oecount, cvec, j, c); ++j)
+ FOR_EACH_VEC_ELT (oecount, cvec, j, c)
{
fprintf (dump_file, " %u %s: ", c->cnt,
c->oecode == MULT_EXPR
if (oecode != c->oecode)
continue;
- for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
+ FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1)
{
if (oe1->op == c->op)
{
fprintf (dump_file, "Building (");
print_generic_expr (dump_file, oe1->op, 0);
}
- tmpvar = create_tmp_var (TREE_TYPE (oe1->op), NULL);
+ tmpvar = create_tmp_reg (TREE_TYPE (oe1->op), NULL);
add_referenced_var (tmpvar);
zero_one_operation (&oe1->op, c->oecode, c->op);
EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0)
}
zero_one_operation (&oe2->op, c->oecode, c->op);
sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode);
- oe2->op = fold_convert (TREE_TYPE (oe2->op), integer_zero_node);
+ oe2->op = build_zero_cst (TREE_TYPE (oe2->op));
oe2->rank = 0;
oe1->op = gimple_get_lhs (sum);
}
return changed;
}
+/* If OPCODE is BIT_IOR_EXPR or BIT_AND_EXPR and CURR is a comparison
+ expression, examine the other OPS to see if any of them are comparisons
+ of the same values, which we may be able to combine or eliminate.
+ For example, we can rewrite (a < b) | (a == b) as (a <= b). */
+
+static bool
+eliminate_redundant_comparison (enum tree_code opcode,
+ VEC (operand_entry_t, heap) **ops,
+ unsigned int currindex,
+ operand_entry_t curr)
+{
+ tree op1, op2;
+ enum tree_code lcode, rcode;
+ gimple def1, def2;
+ int i;
+ operand_entry_t oe;
+
+ if (opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
+ return false;
+
+ /* Check that CURR is a comparison. */
+ if (TREE_CODE (curr->op) != SSA_NAME)
+ return false;
+ def1 = SSA_NAME_DEF_STMT (curr->op);
+ if (!is_gimple_assign (def1))
+ return false;
+ lcode = gimple_assign_rhs_code (def1);
+ if (TREE_CODE_CLASS (lcode) != tcc_comparison)
+ return false;
+ op1 = gimple_assign_rhs1 (def1);
+ op2 = gimple_assign_rhs2 (def1);
+
+ /* Now look for a similar comparison in the remaining OPS. */
+ for (i = currindex + 1;
+ VEC_iterate (operand_entry_t, *ops, i, oe);
+ i++)
+ {
+ tree t;
+
+ if (TREE_CODE (oe->op) != SSA_NAME)
+ continue;
+ def2 = SSA_NAME_DEF_STMT (oe->op);
+ if (!is_gimple_assign (def2))
+ continue;
+ rcode = gimple_assign_rhs_code (def2);
+ if (TREE_CODE_CLASS (rcode) != tcc_comparison)
+ continue;
+
+ /* If we got here, we have a match. See if we can combine the
+ two comparisons. */
+ if (opcode == BIT_IOR_EXPR)
+ t = maybe_fold_or_comparisons (lcode, op1, op2,
+ rcode, gimple_assign_rhs1 (def2),
+ gimple_assign_rhs2 (def2));
+ else
+ t = maybe_fold_and_comparisons (lcode, op1, op2,
+ rcode, gimple_assign_rhs1 (def2),
+ gimple_assign_rhs2 (def2));
+ if (!t)
+ continue;
+
+ /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
+ always give us a boolean_type_node value back. If the original
+ BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
+ we need to convert. */
+ if (!useless_type_conversion_p (TREE_TYPE (curr->op), TREE_TYPE (t)))
+ t = fold_convert (TREE_TYPE (curr->op), t);
+
+ if (TREE_CODE (t) != INTEGER_CST
+ && !operand_equal_p (t, curr->op, 0))
+ {
+ enum tree_code subcode;
+ tree newop1, newop2;
+ if (!COMPARISON_CLASS_P (t))
+ continue;
+ extract_ops_from_tree (t, &subcode, &newop1, &newop2);
+ STRIP_USELESS_TYPE_CONVERSION (newop1);
+ STRIP_USELESS_TYPE_CONVERSION (newop2);
+ if (!is_gimple_val (newop1) || !is_gimple_val (newop2))
+ continue;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Equivalence: ");
+ print_generic_expr (dump_file, curr->op, 0);
+ fprintf (dump_file, " %s ", op_symbol_code (opcode));
+ print_generic_expr (dump_file, oe->op, 0);
+ fprintf (dump_file, " -> ");
+ print_generic_expr (dump_file, t, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ /* Now we can delete oe, as it has been subsumed by the new combined
+ expression t. */
+ VEC_ordered_remove (operand_entry_t, *ops, i);
+ reassociate_stats.ops_eliminated ++;
+
+ /* If t is the same as curr->op, we're done. Otherwise we must
+ replace curr->op with t. Special case is if we got a constant
+ back, in which case we add it to the end instead of in place of
+ the current entry. */
+ if (TREE_CODE (t) == INTEGER_CST)
+ {
+ VEC_ordered_remove (operand_entry_t, *ops, currindex);
+ add_to_ops_vec (ops, t);
+ }
+ else if (!operand_equal_p (t, curr->op, 0))
+ {
+ tree tmpvar;
+ gimple sum;
+ enum tree_code subcode;
+ tree newop1;
+ tree newop2;
+ gcc_assert (COMPARISON_CLASS_P (t));
+ tmpvar = create_tmp_var (TREE_TYPE (t), NULL);
+ add_referenced_var (tmpvar);
+ extract_ops_from_tree (t, &subcode, &newop1, &newop2);
+ STRIP_USELESS_TYPE_CONVERSION (newop1);
+ STRIP_USELESS_TYPE_CONVERSION (newop2);
+ gcc_checking_assert (is_gimple_val (newop1)
+ && is_gimple_val (newop2));
+ sum = build_and_add_sum (tmpvar, newop1, newop2, subcode);
+ curr->op = gimple_get_lhs (sum);
+ }
+ return true;
+ }
+
+ return false;
+}
/* Perform various identities and other optimizations on the list of
operand entries, stored in OPS. The tree code for the binary
if (eliminate_not_pairs (opcode, ops, i, oe))
return;
if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
- || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))
+ || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe))
+ || (!done && eliminate_redundant_comparison (opcode, ops, i, oe)))
{
if (done)
return;
if (TREE_CODE (binlhs) == SSA_NAME)
{
binlhsdef = SSA_NAME_DEF_STMT (binlhs);
- binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop);
+ binlhsisreassoc = (is_reassociable_op (binlhsdef, rhscode, loop)
+ && !stmt_could_throw_p (binlhsdef));
}
if (TREE_CODE (binrhs) == SSA_NAME)
{
binrhsdef = SSA_NAME_DEF_STMT (binrhs);
- binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop);
+ binrhsisreassoc = (is_reassociable_op (binrhsdef, rhscode, loop)
+ && !stmt_could_throw_p (binrhsdef));
}
/* If the LHS is not reassociable, but the RHS is, we need to swap
unsigned int i = 0;
tree negate;
- for (i = 0; VEC_iterate (tree, plus_negates, i, negate); i++)
+ FOR_EACH_VEC_ELT (tree, plus_negates, i, negate)
{
gimple user = get_single_immediate_use (negate);
can_reassociate_p (tree op)
{
tree type = TREE_TYPE (op);
- if (INTEGRAL_TYPE_P (type)
+ if ((INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_WRAPS (type))
|| NON_SAT_FIXED_POINT_TYPE_P (type)
- || (flag_associative_math && SCALAR_FLOAT_TYPE_P (type)))
+ || (flag_associative_math && FLOAT_TYPE_P (type)))
return true;
return false;
}
{
gimple stmt = gsi_stmt (gsi);
- if (is_gimple_assign (stmt))
+ if (is_gimple_assign (stmt)
+ && !stmt_could_throw_p (stmt))
{
tree lhs, rhs1, rhs2;
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
rhs1 = gimple_assign_rhs1 (stmt);
rhs2 = gimple_assign_rhs2 (stmt);
- if (!can_reassociate_p (lhs)
- || !can_reassociate_p (rhs1)
- || !can_reassociate_p (rhs2))
+ /* For non-bit or min/max operations we can't associate
+ all types. Verify that here. */
+ if (rhs_code != BIT_IOR_EXPR
+ && rhs_code != BIT_AND_EXPR
+ && rhs_code != BIT_XOR_EXPR
+ && rhs_code != MIN_EXPR
+ && rhs_code != MAX_EXPR
+ && (!can_reassociate_p (lhs)
+ || !can_reassociate_p (rhs1)
+ || !can_reassociate_p (rhs2)))
continue;
if (associative_tree_code (rhs_code))
gimple_set_visited (stmt, true);
linearize_expr_tree (&ops, stmt, true, true);
- qsort (VEC_address (operand_entry_t, ops),
- VEC_length (operand_entry_t, ops),
- sizeof (operand_entry_t),
- sort_by_operand_rank);
+ VEC_qsort (operand_entry_t, ops, sort_by_operand_rank);
optimize_ops_list (rhs_code, &ops);
if (undistribute_ops_list (rhs_code, &ops,
loop_containing_stmt (stmt)))
{
- qsort (VEC_address (operand_entry_t, ops),
- VEC_length (operand_entry_t, ops),
- sizeof (operand_entry_t),
- sort_by_operand_rank);
+ VEC_qsort (operand_entry_t, ops, sort_by_operand_rank);
optimize_ops_list (rhs_code, &ops);
}
operand_entry_t oe;
unsigned int i;
- for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
+ FOR_EACH_VEC_ELT (operand_entry_t, ops, i, oe)
{
fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
print_generic_expr (file, oe->op, 0);
/* Dump the operand entry vector OPS to STDERR. */
-void
+DEBUG_FUNCTION void
debug_ops_vector (VEC (operand_entry_t, heap) *ops)
{
dump_ops_vector (stderr, ops);
/* Give each argument a distinct rank. */
for (param = DECL_ARGUMENTS (current_function_decl);
param;
- param = TREE_CHAIN (param))
+ param = DECL_CHAIN (param))
{
if (gimple_default_def (cfun, param) != NULL)
{
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+ TODO_verify_ssa
+ | TODO_verify_flow
+ | TODO_dump_func
+ | TODO_ggc_collect /* todo_flags_finish */
}
};
OSDN Git Service
