This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Create less garbage in dominator optimzier
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 25 Nov 2003 14:24:38 -0700
- Subject: [tree-ssa] Create less garbage in dominator optimzier
- Reply-to: law at redhat dot com
We're still creating far too many garbage nodes in the dominator optimizer.
For example, given two constants if we want to compare them we previously
built a comparison node and folded it. Ick.
tree_int_cst_{eq,compare,lt} are a lot more efficient :-)
It was also rather silly to build a MODIFY_EXPR node for eq_expr_value since
all we want out of it is the source & destination.
The net result is another 25k useless nodes eliminated. About a megabyte
in savings.
* tree-ssa-dom.c (get_eq_expr_value): Return a struct rather than
a tree node.
(record_equivalences_from_incoming_edge): Corresponding changes.
(find_equivalent_equality_comparison): Use tree_int_cst_XXX rather
then building and folding nodes.
(simplify_cond_and_lookup_avail_expr): Likewise.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.86
diff -c -p -r1.1.2.86 tree-ssa-dom.c
*** tree-ssa-dom.c 22 Nov 2003 04:13:49 -0000 1.1.2.86
--- tree-ssa-dom.c 25 Nov 2003 19:35:32 -0000
*************** struct dom_walk_block_data
*** 192,204 ****
varray_type vrp_variables;
};
/* Local functions. */
static bool optimize_stmt (block_stmt_iterator, varray_type *, varray_type
*);
static inline tree get_value_for (tree, varray_type table);
static inline void set_value_for (tree, tree, varray_type table);
static tree lookup_avail_expr (tree, varray_type *, bool);
! static tree get_eq_expr_value (tree, int, varray_type *, varray_type *,
! basic_block, varray_type *);
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static hashval_t true_false_expr_hash (const void *);
--- 192,211 ----
varray_type vrp_variables;
};
+ struct eq_expr_value
+ {
+ tree src;
+ tree dst;
+ };
+
/* Local functions. */
static bool optimize_stmt (block_stmt_iterator, varray_type *, varray_type
*);
static inline tree get_value_for (tree, varray_type table);
static inline void set_value_for (tree, tree, varray_type table);
static tree lookup_avail_expr (tree, varray_type *, bool);
! static struct eq_expr_value get_eq_expr_value (tree, int, varray_type *,
! varray_type *, basic_block,
! varray_type *);
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static hashval_t true_false_expr_hash (const void *);
*************** record_equivalences_from_incoming_edge (
*** 936,945 ****
tree parent_block_last_stmt)
{
int edge_flags;
! tree eq_expr_value = NULL_TREE;
struct dom_walk_block_data *bd
= (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
/* If we have a single predecessor, then extract EDGE_FLAGS from
our single incoming edge. Otherwise clear EDGE_FLAGS and
PARENT_BLOCK_LAST_STMT since they're not needed. */
--- 943,955 ----
tree parent_block_last_stmt)
{
int edge_flags;
! struct eq_expr_value eq_expr_value;
struct dom_walk_block_data *bd
= (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
+ eq_expr_value.src = NULL;
+ eq_expr_value.dst = NULL;
+
/* If we have a single predecessor, then extract EDGE_FLAGS from
our single incoming edge. Otherwise clear EDGE_FLAGS and
PARENT_BLOCK_LAST_STMT since they're not needed. */
*************** record_equivalences_from_incoming_edge (
*** 1017,1024 ****
&& CASE_LOW (match_case)
&& !CASE_HIGH (match_case))
{
! eq_expr_value = build (MODIFY_EXPR, TREE_TYPE (switch_cond),
! switch_cond, CASE_LOW (match_case));
}
}
}
--- 1027,1034 ----
&& CASE_LOW (match_case)
&& !CASE_HIGH (match_case))
{
! eq_expr_value.dst = switch_cond;
! eq_expr_value.src = CASE_LOW (match_case);
}
}
}
*************** record_equivalences_from_incoming_edge (
*** 1027,1036 ****
/* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
new value for VAR, so that occurrences of VAR can be replaced with
VALUE while re-writing the THEN arm of a COND_EXPR. */
! if (eq_expr_value)
{
! tree dest = TREE_OPERAND (eq_expr_value, 0);
! tree src = TREE_OPERAND (eq_expr_value, 1);
tree prev_value = get_value_for (dest, const_and_copies);
set_value_for (dest, src, const_and_copies);
--- 1037,1046 ----
/* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
new value for VAR, so that occurrences of VAR can be replaced with
VALUE while re-writing the THEN arm of a COND_EXPR. */
! if (eq_expr_value.src && eq_expr_value.dst)
{
! tree dest = eq_expr_value.dst;
! tree src = eq_expr_value.src;
tree prev_value = get_value_for (dest, const_and_copies);
set_value_for (dest, src, const_and_copies);
*************** find_equivalent_equality_comparison (tre
*** 1508,1516 ****
condition which uses the source of the typecast and the
new constant (which has only changed its type). */
new = fold (build1 (NOP_EXPR, def_rhs_inner_type, op1));
! if (is_gimple_val (new)
! && integer_onep (fold (build (EQ_EXPR, boolean_type_node,
! new, op1))))
return build (TREE_CODE (cond), TREE_TYPE (cond),
def_rhs_inner, new);
}
--- 1518,1524 ----
condition which uses the source of the typecast and the
new constant (which has only changed its type). */
new = fold (build1 (NOP_EXPR, def_rhs_inner_type, op1));
! if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
return build (TREE_CODE (cond), TREE_TYPE (cond),
def_rhs_inner, new);
}
*************** simplify_cond_and_lookup_avail_expr (tre
*** 1664,1674 ****
Similarly the high value for the merged range is the
minimum of the previous high value and the high value of
this record. */
! low = fold (build (MAX_EXPR, TREE_TYPE (low),
! low, tmp_low));
! high = fold (build (MIN_EXPR, TREE_TYPE (high),
! high, tmp_high));
!
}
/* And record the computed range. */
--- 1672,1681 ----
Similarly the high value for the merged range is the
minimum of the previous high value and the high value of
this record. */
! low = (tree_int_cst_compare (low, tmp_low) == 1
! ? low : tmp_low);
! high = (tree_int_cst_compare (high, tmp_high) == -1
! ? high : tmp_high);
}
/* And record the computed range. */
*************** simplify_cond_and_lookup_avail_expr (tre
*** 1684,1693 ****
low value is the same low value as the conditional.
Similarly for the current high value and the high value
for the conditional. */
! lowequal = integer_onep (fold (build (EQ_EXPR, boolean_type_node,
! low, cond_low)));
! highequal = integer_onep (fold (build (EQ_EXPR, boolean_type_node,
! high, cond_high)));
if (lowequal && highequal)
return (cond_inverted ? boolean_false_node : boolean_true_node);
--- 1691,1698 ----
low value is the same low value as the conditional.
Similarly for the current high value and the high value
for the conditional. */
! lowequal = tree_int_cst_equal (low, cond_low);
! highequal = tree_int_cst_equal (high, cond_high);
if (lowequal && highequal)
return (cond_inverted ? boolean_false_node : boolean_true_node);
*************** simplify_cond_and_lookup_avail_expr (tre
*** 1696,1706 ****
to swap the two ranges so that the larger of the two
ranges occurs "first". */
swapped = 0;
! if (integer_onep (fold (build (GT_EXPR, boolean_type_node,
! low, cond_low)))
|| (lowequal
! && integer_onep (fold (build (GT_EXPR, boolean_type_node,
! cond_high, high)))))
{
tree temp;
--- 1701,1709 ----
to swap the two ranges so that the larger of the two
ranges occurs "first". */
swapped = 0;
! if (tree_int_cst_compare (low, cond_low) == 1
|| (lowequal
! && tree_int_cst_compare (cond_high, high) == 1))
{
tree temp;
*************** simplify_cond_and_lookup_avail_expr (tre
*** 1715,1725 ****
/* Now determine if there is no overlap in the ranges
or if the second range is a subset of the first range. */
! no_overlap = integer_onep (fold (build (LT_EXPR,
! boolean_type_node,
! high, cond_low)));
! subset = integer_onep (fold (build (LE_EXPR, boolean_type_node,
! cond_high, high)));
/* If there was no overlap in the ranges, then this conditional
always has a false value (unless we had to invert this
--- 1718,1725 ----
/* Now determine if there is no overlap in the ranges
or if the second range is a subset of the first range. */
! no_overlap = tree_int_cst_lt (high, cond_low);
! subset = tree_int_cst_compare (cond_high, high) != 1;
/* If there was no overlap in the ranges, then this conditional
always has a false value (unless we had to invert this
*************** simplify_cond_and_lookup_avail_expr (tre
*** 1737,1751 ****
/* We were unable to determine the result of the conditional.
However, we may be able to simplify the conditional. First
merge the ranges in the same manner as range merging above. */
! low = fold (build (MAX_EXPR, TREE_TYPE (low), low, cond_low));
! high = fold (build (MIN_EXPR, TREE_TYPE (high), high, cond_high));
/* If the range has converged to a single point, then turn this
into an equality comparison. */
if (TREE_CODE (cond) != EQ_EXPR
&& TREE_CODE (cond) != NE_EXPR
! && integer_onep (fold (build (EQ_EXPR, boolean_type_node,
! high, low))))
{
TREE_SET_CODE (cond, EQ_EXPR);
TREE_OPERAND (cond, 1) = high;
--- 1737,1750 ----
/* We were unable to determine the result of the conditional.
However, we may be able to simplify the conditional. First
merge the ranges in the same manner as range merging above. */
! low = tree_int_cst_compare (low, cond_low) == 1 ? low : cond_low;
! high = tree_int_cst_compare (high, cond_high) == -1 ? high : cond_high;
/* If the range has converged to a single point, then turn this
into an equality comparison. */
if (TREE_CODE (cond) != EQ_EXPR
&& TREE_CODE (cond) != NE_EXPR
! && tree_int_cst_equal (low, high))
{
TREE_SET_CODE (cond, EQ_EXPR);
TREE_OPERAND (cond, 1) = high;
*************** record_range (tree cond, basic_block bb,
*** 2550,2556 ****
This allows us to lookup the condition in a dominated block and
get back a constant indicating if the condition is true. */
! static tree
get_eq_expr_value (tree if_stmt,
int true_arm,
varray_type *block_true_exprs_p,
--- 2549,2555 ----
This allows us to lookup the condition in a dominated block and
get back a constant indicating if the condition is true. */
! static struct eq_expr_value
get_eq_expr_value (tree if_stmt,
int true_arm,
varray_type *block_true_exprs_p,
*************** get_eq_expr_value (tree if_stmt,
*** 2558,2573 ****
basic_block bb,
varray_type *vrp_variables_p)
{
! tree cond, value;
cond = COND_EXPR_COND (if_stmt);
! value = NULL;
/* If the conditional is a single variable 'X', return 'X = 1' for
the true arm and 'X = 0' on the false arm. */
if (TREE_CODE (cond) == SSA_NAME)
! return build (MODIFY_EXPR, TREE_TYPE (cond), cond,
! (true_arm ? integer_one_node : integer_zero_node));
/* If we have a comparison expression, then record its result into
the available expression table. */
--- 2557,2577 ----
basic_block bb,
varray_type *vrp_variables_p)
{
! tree cond;
! struct eq_expr_value retval;
cond = COND_EXPR_COND (if_stmt);
! retval.src = NULL;
! retval.dst = NULL;
/* If the conditional is a single variable 'X', return 'X = 1' for
the true arm and 'X = 0' on the false arm. */
if (TREE_CODE (cond) == SSA_NAME)
! {
! retval.dst = cond;
! retval.src = (true_arm ? integer_one_node : integer_zero_node);
! return retval;
! }
/* If we have a comparison expression, then record its result into
the available expression table. */
*************** get_eq_expr_value (tree if_stmt,
*** 2600,2606 ****
/* If the conditional is of the form 'X == Y', return 'X = Y'
for the true arm. */
if (TREE_CODE (cond) == EQ_EXPR)
! value = build (MODIFY_EXPR, TREE_TYPE (cond), op0, op1);
}
else
{
--- 2604,2614 ----
/* If the conditional is of the form 'X == Y', return 'X = Y'
for the true arm. */
if (TREE_CODE (cond) == EQ_EXPR)
! {
! retval.dst = op0;
! retval.src = op1;
! return retval;
! }
}
else
{
*************** get_eq_expr_value (tree if_stmt,
*** 2614,2625 ****
/* If the conditional is of the form 'X != Y', return 'X = Y'
for the false arm. */
if (TREE_CODE (cond) == NE_EXPR)
! value = build (MODIFY_EXPR, TREE_TYPE (cond), op0, op1);
}
}
}
! return value;
}
/* Hashing for expressions which are going to be entered into the true/false
--- 2622,2637 ----
/* If the conditional is of the form 'X != Y', return 'X = Y'
for the false arm. */
if (TREE_CODE (cond) == NE_EXPR)
! {
! retval.dst = op0;
! retval.src = op1;
! return retval;
! }
}
}
}
! return retval;
}
/* Hashing for expressions which are going to be entered into the true/false