On Mon, 13 Jul 2015, Richard Biener wrote:
> On Sun, 12 Jul 2015, Jeff Law wrote:
>
> > On 06/29/2015 01:58 AM, Richard Biener wrote:
> > >
> > > In principle the following works for the testcase (even w/o fixing
> > > the VRP part).
> > >
> > > Index: gcc/tree-ssa-dom.c
> > > ===================================================================
> > > --- gcc/tree-ssa-dom.c (revision 225007)
> > > +++ gcc/tree-ssa-dom.c (working copy)
> > > @@ -1409,6 +1409,14 @@ simplify_stmt_for_jump_threading (gimple
> > > return lookup_avail_expr (stmt, false);
> > > }
> > >
> > > +static tree
> > > +dom_valueize (tree t)
> > > +{
> > > + if (TREE_CODE (t) == SSA_NAME)
> > > + return SSA_NAME_VALUE (t);
> > > + return t;
> > > +}
> > > +
> > > /* Record into the equivalence tables any equivalences implied by
> > > traversing edge E (which are cached in E->aux).
> > >
> > > @@ -1429,7 +1437,33 @@ record_temporary_equivalences (edge e)
> > >
> > > /* If we have a simple NAME = VALUE equivalence, record it. */
> > > if (lhs && TREE_CODE (lhs) == SSA_NAME)
> > > - const_and_copies->record_const_or_copy (lhs, rhs);
> > > + {
> > > + gimple use_stmt;
> > > + imm_use_iterator iter;
> > > + const_and_copies->record_const_or_copy (lhs, rhs);
> > > + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
> > > + {
> > > + /* Only bother to record more equivalences for lhs that
> > > + can be directly used by e->dest.
> > > + ??? If the code gets re-organized to a worklist to
> > > + catch more indirect opportunities and it is made to
> > > + handle PHIs then this should only consider use_stmts
> > > + in basic-blocks we have already visited. */
> > > + if (!dominated_by_p (CDI_DOMINATORS,
> > > + e->dest, gimple_bb (use_stmt)))
> > > + continue;
> > > + tree lhs = gimple_get_lhs (use_stmt);
> > > + if (lhs && TREE_CODE (lhs) == SSA_NAME)
> > > + {
> > > + tree res = gimple_fold_stmt_to_constant_1 (use_stmt,
> > > + dom_valueize,
> > > +
> > > no_follow_ssa_edges);
> > > + if (TREE_CODE (res) == SSA_NAME
> > > + || is_gimple_min_invariant (res))
> > > + const_and_copies->record_const_or_copy (lhs, res);
> > > + }
> > > + }
> > > + }
> > >
> > > /* If we have 0 = COND or 1 = COND equivalences, record them
> > > into our expression hash tables. */
> > >
> > >
> > > it's not using DOMs own stmt visiting machinery as that always modifies
> > > stmts in-place. As stated in the comment it doesn't catch secondary
> > > opportunities. That would be possible by using a work-list seeded
> > > by LHS we recorded new const/copies for and re-visiting their uses.
> > > You can get extra fancy here by properly handling PHIs and
> > > conditionals. But it's a question of cost here, of course.
> > Right, the code you're modifying is only used by jump threading to record
> > temporary equivalences, particularly equivalences that are specific to a
> > path.
> >
> >
> > >
> > > Note that I think this isn't really "backward propagation" but
> > > just context sensitive value-numbering.
> > I think that's because we're looking at the problem differently. It's
> > certainly not backward propagation in the traditional dataflow sense, so I'm
> > probably being too loose with terminology here.
> >
> > When we discover something about X by means other than the definition of X,
> > we
> > can look at how X was set and possibly discover a value for source operands
> > of
> > that statement. Similarly we can look at uses of X and possibly discover a
> > value for the destination of those statement(s). In both cases we're going
> > backwards from an order-of-execution point of view and recording additional
> > equivalences.
> >
> > The existing code did the former (look at X's defining statement and try to
> > discover an equivalence for a source operand in that statement). What we
> > need
> > to optimize this case is the latter.
> >
> > I *think* these are closely enough related that some code can be factored
> > out
> > a bit and reused in both r_e_f_i_e and r_t_e to discover both types of
> > equivalences for DOM and for jump threading.
>
> Indeed - the odd thing here is that one function uses
> const_and_copies->record_const_or_copy directly while the other one
> record_equality (this function is _solely_ used by
> record_equivalences_from_incoming_edge). I didn't want to introduce
> a callback to commonize the code (though in principle we could use
> a template function with a function template parameter...)
>
> That said, I don't see that record_equality does sth not suitable
> if called from record_temporary_equivalences. So if we make
> use of that function we could simply call record_temporary_equivalences
> from record_equivalences_from_incoming_edge.
So, like the following.
Bootstrapped on x86_64-unknown-linux-gnu - ok if testing succeeds?
Thanks,
Richard.
2015-07-13 Richard Biener <[email protected]>
* tree-ssa-dom.c (record_temporary_equivalences): Merge
wideing type conversion case from record_equivalences_from_incoming_edge
and use record_equality to record equivalences.
(record_equivalences_from_incoming_edge): Call
record_temporary_equivalences.
Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c (revision 225727)
+++ gcc/tree-ssa-dom.c (working copy)
@@ -1420,8 +1420,41 @@ record_temporary_equivalences (edge e)
tree rhs = edge_info->rhs;
/* If we have a simple NAME = VALUE equivalence, record it. */
- if (lhs && TREE_CODE (lhs) == SSA_NAME)
- const_and_copies->record_const_or_copy (lhs, rhs);
+ if (lhs)
+ record_equality (lhs, rhs);
+
+ /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
+ set via a widening type conversion, then we may be able to record
+ additional equivalences. */
+ if (lhs
+ && TREE_CODE (lhs) == SSA_NAME
+ && is_gimple_constant (rhs)
+ && TREE_CODE (rhs) == INTEGER_CST)
+ {
+ gimple defstmt = SSA_NAME_DEF_STMT (lhs);
+
+ if (defstmt
+ && is_gimple_assign (defstmt)
+ && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt)))
+ {
+ tree old_rhs = gimple_assign_rhs1 (defstmt);
+
+ /* If the conversion widens the original value and
+ the constant is in the range of the type of OLD_RHS,
+ then convert the constant and record the equivalence.
+
+ Note that int_fits_type_p does not check the precision
+ if the upper and lower bounds are OK. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs))
+ && (TYPE_PRECISION (TREE_TYPE (lhs))
+ > TYPE_PRECISION (TREE_TYPE (old_rhs)))
+ && int_fits_type_p (rhs, TREE_TYPE (old_rhs)))
+ {
+ tree newval = fold_convert (TREE_TYPE (old_rhs), rhs);
+ record_equality (old_rhs, newval);
+ }
+ }
+ }
/* If we have 0 = COND or 1 = COND equivalences, record them
into our expression hash tables. */
@@ -1568,7 +1601,6 @@ record_equivalences_from_incoming_edge (
{
edge e;
basic_block parent;
- struct edge_info *edge_info;
/* If our parent block ended with a control statement, then we may be
able to record some equivalences based on which outgoing edge from
@@ -1580,57 +1612,7 @@ record_equivalences_from_incoming_edge (
/* If we had a single incoming edge from our parent block, then enter
any data associated with the edge into our tables. */
if (e && e->src == parent)
- {
- unsigned int i;
-
- edge_info = (struct edge_info *) e->aux;
-
- if (edge_info)
- {
- tree lhs = edge_info->lhs;
- tree rhs = edge_info->rhs;
- cond_equivalence *eq;
-
- if (lhs)
- record_equality (lhs, rhs);
-
- /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
- set via a widening type conversion, then we may be able to record
- additional equivalences. */
- if (lhs
- && TREE_CODE (lhs) == SSA_NAME
- && is_gimple_constant (rhs)
- && TREE_CODE (rhs) == INTEGER_CST)
- {
- gimple defstmt = SSA_NAME_DEF_STMT (lhs);
-
- if (defstmt
- && is_gimple_assign (defstmt)
- && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt)))
- {
- tree old_rhs = gimple_assign_rhs1 (defstmt);
-
- /* If the conversion widens the original value and
- the constant is in the range of the type of OLD_RHS,
- then convert the constant and record the equivalence.
-
- Note that int_fits_type_p does not check the precision
- if the upper and lower bounds are OK. */
- if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs))
- && (TYPE_PRECISION (TREE_TYPE (lhs))
- > TYPE_PRECISION (TREE_TYPE (old_rhs)))
- && int_fits_type_p (rhs, TREE_TYPE (old_rhs)))
- {
- tree newval = fold_convert (TREE_TYPE (old_rhs), rhs);
- record_equality (old_rhs, newval);
- }
- }
- }
-
- for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
- record_cond (eq);
- }
- }
+ record_temporary_equivalences (e);
}
/* Dump SSA statistics on FILE. */
