[tree-ssa] More dominator improvements
law@redhat.com
law@redhat.com
Wed Jul 16 22:01:00 GMT 2003
Let's consider the following code (20030711-1.c):
/* { dg-do compile */
/* { dg-options "-O1 -fdump-tree-ssa" } */
union tree_node;
typedef union tree_node *tree;
struct tree_vec
{
int length;
tree a[1];
};
struct tree_type
{
tree binfo;
};
union tree_node
{
struct tree_type type;
struct tree_vec vec;
};
void
record_component_aliases (type)
tree type;
{
int i;
if (4 >= type->type.binfo->vec.length)
abort ();
for (; i < ((
{
const tree __t = type->type.binfo;
if (4 >= __t->vec.length)
abort (); type->type.binfo->vec.a[4];}
)->vec.length);)
{
if (4 >= type->type.binfo->vec.length)
abort ();
blah ();
}
}
/* The call to blah can not be eliminated.
/* { dg-final { scan-tree-dump-times "blah \\(\\)" 1 "ssa" } } */
/* There should be three IF conditionals. */
/* { dg-final { scan-tree-dump-times "if " 3 "ssa"} } */
/* There should be two loads of type.binfo. */
/* { dg-final { scan-tree-dump-times "type\\.binfo" 2 "ssa"} } */
/* There should be three loads of vec.length. */
/* { dg-final { scan-tree-dump-times "vec.length" 3 "ssa"} } */
Which generates the following gimple code:
record_component_aliases (type)
{
union tree_node * T.1;
int T.2;
union tree_node * retval.3;
int T.4;
int T.5;
int i;
extern abort;
T.1 = type->type.binfo;
T.2 = T.1->vec.length;
if (T.2 <= 4)
{
abort ()
}
else
{
(void)0
};
while (1)
{
{
union tree_node * const __t;
__t = type->type.binfo;
T.4 = __t->vec.length;
if (T.4 <= 4)
{
abort ()
}
else
{
(void)0
};
T.1 = type->type.binfo;
retval.3 = T.1->vec.a[4]
};
T.5 = retval.3->vec.length;
if (i >= T.5)
{
goto <ULce70>;
}
else
{
(void)0
};
{
extern blah;
T.1 = type->type.binfo;
T.2 = T.1->vec.length;
if (T.2 <= 4)
{
abort ()
}
else
{
(void)0
};
blah ()
}
};
<ULce70>:;
}
Analysis of this code should lead you to realize that the last conditional
(T.2 <= 4) is known to be false as there is an earlier conditional with the
same condition which aborts if the condition is false (first condition inside
the while loop testing T.2 <= 4). Thus we should remove the last conditional.
Unfortunately, we don't (and it is something that the expensive path following
code in cse1 would catch)
You might think that the test outside the loop (T.2 <= 4) would tell
us something about the first test inside the loop of (T.4 <= 4) since
they seem to both get their temporaries from type->type.binfo->vec.length.
However, that would be incorrect since there is a reachable call inside
the loop which may modify global memory -- thus type->type.binfo->vec.length
can vary during the loop.
Anyway removal of the useless conditional isn't terribly hard. When
we dive into a conditional we also want to record things into the
available_exprs table. Given a conditional which tests <cond> we
want to note that <cond> has the value 1 in the true arm of the
conditional and 0 in the false arm (and some inverses too).
One approach would be to do something like this:
Enter temp0 = 1 into the const_and_copies table
Enter temp0 = <cond> into the available expression table.
Thus when we lookup <cond> in the expression table, we get back temp0, which
we then lookup in the const_and_copies table, giving us the constant value 1.
That can be made to work (in fact, that's what my original implementation
did), but it's a pain.
It's easier (and faster) to simply put 1 = <cond> into the available expression
table. This works because when we get a hit in the expression table, we use
the LHS of the "statement" in the expression table as a replacement for the
later evaluation of the expression. ie, we use the constant 1 instead
of <cond> in later evaluations of <cond>.
Note we do not generate statements which appear in the IL -- these
"statements" appear only in the available expression hash table to record
certain equivalences we know because of the conditions we tested to
get to a particular point in the function.
Anyway, this fixes two more of the failures in the new tree-ssa tests.
Bootstrapped and regression tested i686-pc-linux-gnu.
* tree-ssa-dom.c (get_eq_expr_value): Also enter expressions
into the available expression hash table. Callers changed to
pass in the block_avail_exprs varray and const_and_copies hash
table.
(optimize_stmt): Allow optimization of the condition in
a COND_EXPR statement.
(lookup_avail_expr): For COND_EXPRs, just see if their condition
has been recorded into the hash table, do not enter them into
the hash table. Only do a lookup of the result in the
const_and_copies table if it is an SSA_VAR.
(avail_expr_hash): Handle COND_EXPRs, specifically we only care
about their condition and virtual operands.
(avail_expr_eq): Likewise. If one statement has virtual operands
and the other does not, then the expressions are not equal.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 tree-ssa-dom.c
*** tree-ssa-dom.c 16 Jul 2003 19:26:53 -0000 1.1.2.3
--- tree-ssa-dom.c 16 Jul 2003 20:31:54 -0000
*************** static void set_value_for (tree, tree, h
*** 88,94 ****
static hashval_t var_value_hash (const void *);
static int var_value_eq (const void *, const void *);
static tree lookup_avail_expr (tree, varray_type *, htab_t);
! static tree get_eq_expr_value (tree, int);
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
--- 88,94 ----
static hashval_t var_value_hash (const void *);
static int var_value_eq (const void *, const void *);
static tree lookup_avail_expr (tree, varray_type *, htab_t);
! static tree get_eq_expr_value (tree, int, varray_type *, htab_t);
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
*************** optimize_block (basic_block bb, tree par
*** 186,192 ****
&& TREE_CODE (parent_block_last_stmt) == COND_EXPR
&& (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
! (edge_flags & EDGE_TRUE_VALUE) != 0);
/* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
--- 186,194 ----
&& TREE_CODE (parent_block_last_stmt) == COND_EXPR
&& (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
! (edge_flags & EDGE_TRUE_VALUE) != 0,
! &block_avail_exprs,
! const_and_copies);
/* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
*************** optimize_stmt (block_stmt_iterator si, v
*** 409,422 ****
/* Check for redundant computations. Do this optimization only
for assignments that make no calls and have no aliased stores
nor volatile references and no side effects (i.e., no VDEFs). */
! may_optimize_p = !ann->makes_aliased_stores
! && !ann->has_volatile_ops
! && vdefs == NULL
! && def_p
! && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1));
if (may_optimize_p)
{
/* Check if the RHS of the assignment has been computed before. If
so, use the LHS of the previously computed statement as the
reaching definition for the variable defined by this statement. */
--- 411,427 ----
/* Check for redundant computations. Do this optimization only
for assignments that make no calls and have no aliased stores
nor volatile references and no side effects (i.e., no VDEFs). */
! may_optimize_p = (!ann->makes_aliased_stores
! && !ann->has_volatile_ops
! && vdefs == NULL
! && ((def_p
! && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
! || TREE_CODE (stmt) == COND_EXPR));
if (may_optimize_p)
{
+ tree *expr_p;
+
/* Check if the RHS of the assignment has been computed before. If
so, use the LHS of the previously computed statement as the
reaching definition for the variable defined by this statement. */
*************** optimize_stmt (block_stmt_iterator si, v
*** 425,445 ****
const_and_copies);
opt_stats.num_exprs_considered++;
if (cached_lhs
! && (TREE_TYPE (cached_lhs) == TREE_TYPE (*def_p)
|| (TYPE_MAIN_VARIANT (TREE_TYPE (cached_lhs))
== TYPE_MAIN_VARIANT (TREE_TYPE (*def_p)))))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Replaced redundant expr '");
! print_generic_expr (dump_file, TREE_OPERAND (stmt, 1), 0);
fprintf (dump_file, "' with '");
print_generic_expr (dump_file, cached_lhs, 0);
fprintf (dump_file, "'\n");
}
opt_stats.num_re++;
! TREE_OPERAND (stmt, 1) = cached_lhs;
ann->modified = 1;
}
}
--- 430,456 ----
const_and_copies);
opt_stats.num_exprs_considered++;
if (cached_lhs
! && (TREE_CODE (stmt) == COND_EXPR
! || TREE_TYPE (cached_lhs) == TREE_TYPE (*def_p)
|| (TYPE_MAIN_VARIANT (TREE_TYPE (cached_lhs))
== TYPE_MAIN_VARIANT (TREE_TYPE (*def_p)))))
{
+ if (TREE_CODE (stmt) == COND_EXPR)
+ expr_p = &TREE_OPERAND (stmt, 0);
+ else
+ expr_p = &TREE_OPERAND (stmt, 1);
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " Replaced redundant expr '");
! print_generic_expr (dump_file, *expr_p, 0);
fprintf (dump_file, "' with '");
print_generic_expr (dump_file, cached_lhs, 0);
fprintf (dump_file, "'\n");
}
opt_stats.num_re++;
! *expr_p = cached_lhs;
ann->modified = 1;
}
}
*************** lookup_avail_expr (tree stmt,
*** 544,560 ****
tree rhs;
tree lhs;
tree temp;
/* Don't bother remembering constant assignments and copy operations.
Constants and copy operations are handled by the constant/copy
propagator
in optimize_stmt. */
- rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE (rhs) == SSA_NAME
|| is_unchanging_value (rhs)
|| is_optimizable_addr_expr (rhs))
return NULL_TREE;
! slot = htab_find_slot (avail_exprs, stmt, INSERT);
if (*slot == NULL)
{
*slot = (void *) stmt;
--- 555,589 ----
tree rhs;
tree lhs;
tree temp;
+ int insert;
+
+ /* For a COND_EXPR, the expression we care about is in operand 0, not
+ operand 1. Also note that for a COND_EXPR, we merely want to see if
+ we have the expression in the hash table, we do not want to create
+ a new entry in the hash table. */
+ if (TREE_CODE (stmt) == COND_EXPR)
+ {
+ rhs = TREE_OPERAND (stmt, 0);
+ insert = 0;
+ }
+ else
+ {
+ rhs = TREE_OPERAND (stmt, 1);
+ insert = 1;
+ }
/* Don't bother remembering constant assignments and copy operations.
Constants and copy operations are handled by the constant/copy
propagator
in optimize_stmt. */
if (TREE_CODE (rhs) == SSA_NAME
|| is_unchanging_value (rhs)
|| is_optimizable_addr_expr (rhs))
return NULL_TREE;
! slot = htab_find_slot (avail_exprs, stmt, (insert ? INSERT : NO_INSERT));
! if (slot == NULL)
! return NULL_TREE;
!
if (*slot == NULL)
{
*slot = (void *) stmt;
*************** lookup_avail_expr (tree stmt,
*** 568,576 ****
/* See if the LHS appears in the const_and_copies table. If it does, then
use the value from the const_and_copies table. */
! temp = get_value_for (lhs, const_and_copies);
! if (temp)
! lhs = temp;
return lhs;
}
--- 597,608 ----
/* See if the LHS appears in the const_and_copies table. If it does, then
use the value from the const_and_copies table. */
! if (SSA_VAR_P (lhs))
! {
! temp = get_value_for (lhs, const_and_copies);
! if (temp)
! lhs = temp;
! }
return lhs;
}
*************** lookup_avail_expr (tree stmt,
*** 580,594 ****
known to be true depending on which arm of IF_STMT is taken.
Not all conditional statements will result in a useful assignment.
! Return NULL_TREE in that case. */
static tree
! get_eq_expr_value (tree if_stmt, int true_arm)
{
tree cond, value;
cond = COND_EXPR_COND (if_stmt);
/* If the conditional is a single variable 'X', return 'X = 1' for
the true arm and 'X = 0' on the false arm. */
if (SSA_VAR_P (cond))
--- 612,685 ----
known to be true depending on which arm of IF_STMT is taken.
Not all conditional statements will result in a useful assignment.
! Return NULL_TREE in that case.
!
! Also enter into the available expression table statements of
! the form:
!
! TRUE ARM FALSE ARM
! 1 = cond 1 = cond'
! 0 = cond' 0 = cond
!
! 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_avail_exprs_p, htab_t const_and_copies)
{
tree cond, value;
cond = COND_EXPR_COND (if_stmt);
+ /* If we have a comparison expression, then record its result into
+ the available expression table. */
+ if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
+ {
+ tree temp;
+
+ /* When we find an available expression in the hash table, we replace
+ the expression with the LHS of the statement in the hash table.
+
+ So, we want to build statements such as "1 = <condition>" on the
+ true arm and "0 = <condition>" on the false arm. That way if we
+ find the expression in the table, we will replace it with its
+ known constant value. Also insert inversions of the result and
+ condition into the hash table. */
+ if (true_arm)
+ {
+ /* Insert 1 = cond into the available expression table. */
+ temp = build (MODIFY_EXPR, TREE_TYPE (cond),
+ integer_one_node, cond);
+ temp = lookup_avail_expr (temp,
+ block_avail_exprs_p,
+ const_and_copies);
+
+ /* Insert 0 = cond' into the hash table. */
+ temp = build (MODIFY_EXPR, TREE_TYPE (cond),
+ integer_zero_node, invert_truthvalue (cond));
+ temp = lookup_avail_expr (temp,
+ block_avail_exprs_p,
+ const_and_copies);
+ }
+ else
+ {
+ /* Insert 1 = cond' into the available expression table. */
+ temp = build (MODIFY_EXPR, TREE_TYPE (cond),
+ integer_one_node, invert_truthvalue (cond));
+ temp = lookup_avail_expr (temp,
+ block_avail_exprs_p,
+ const_and_copies);
+
+ /* Insert 0 = cond into the available expression table. */
+ temp = build (MODIFY_EXPR, TREE_TYPE (cond),
+ integer_zero_node, cond);
+ temp = lookup_avail_expr (temp,
+ block_avail_exprs_p,
+ const_and_copies);
+ }
+ }
+
/* If the conditional is a single variable 'X', return 'X = 1' for
the true arm and 'X = 0' on the false arm. */
if (SSA_VAR_P (cond))
*************** avail_expr_hash (const void *p)
*** 640,649 ****
varray_type ops;
tree stmt = (tree) p;
/* iterative_hash_expr knows how to deal with any expression and
deals with commutative operators as well, so just use it instead
of duplicating such complexities here. */
- rhs = TREE_OPERAND (stmt, 1);
val = iterative_hash_expr (rhs, val);
/* Add the SSA version numbers of every vuse operand. This is important
--- 731,746 ----
varray_type ops;
tree stmt = (tree) p;
+ /* If we're hashing a COND_EXPR, the expression we care about is
+ in operand position 0, not position 1. */
+ if (TREE_CODE (stmt) == COND_EXPR)
+ rhs = TREE_OPERAND (stmt, 0);
+ else
+ rhs = TREE_OPERAND (stmt, 1);
+
/* iterative_hash_expr knows how to deal with any expression and
deals with commutative operators as well, so just use it instead
of duplicating such complexities here. */
val = iterative_hash_expr (rhs, val);
/* Add the SSA version numbers of every vuse operand. This is important
*************** avail_expr_eq (const void *p1, const voi
*** 664,673 ****
tree s1, s2, rhs1, rhs2;
s1 = (tree) p1;
! rhs1 = TREE_OPERAND (s1, 1);
s2 = (tree) p2;
! rhs2 = TREE_OPERAND (s2, 1);
/* If they are the same physical statement, return true. */
if (s1 == s2)
--- 761,776 ----
tree s1, s2, rhs1, rhs2;
s1 = (tree) p1;
! if (TREE_CODE (s1) == COND_EXPR)
! rhs1 = TREE_OPERAND (s1, 0);
! else
! rhs1 = TREE_OPERAND (s1, 1);
s2 = (tree) p2;
! if (TREE_CODE (s2) == COND_EXPR)
! rhs2 = TREE_OPERAND (s2, 0);
! else
! rhs2 = TREE_OPERAND (s2, 1);
/* If they are the same physical statement, return true. */
if (s1 == s2)
*************** avail_expr_eq (const void *p1, const voi
*** 692,697 ****
--- 795,806 ----
#endif
return true;
}
+
+ /* If one has virtual operands and the other does not, then we
+ consider them not equal. */
+ if ((ops1 == NULL && ops2 != NULL)
+ || (ops1 != NULL && ops2 == NULL))
+ return false;
if (VARRAY_ACTIVE_SIZE (ops1) == VARRAY_ACTIVE_SIZE (ops2))
{
More information about the Gcc-patches
mailing list