On Mon, 13 Jul 2015, Jeff Law wrote:
> On 07/13/2015 03:32 AM, Richard Biener wrote:
> > 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.
> Yea, if testing is clean, that's OK. Ought to be easier to then add code to
> handle looking at the uses of X to see if they create an equivalence for the
> destination of those use statements.
Applied. The following patch adds the equivalences for the destination
of use stmts if they simplify.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2015-07-14 Richard Biener <[email protected]>
* tree-ssa-dom.c (dom_valueize): New function.
(record_temporary_equivalences): Also record equivalences
for dominating stmts that have uses of equivalences we are
about to record.
Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c (revision 225761)
+++ gcc/tree-ssa-dom.c (working copy)
@@ -1401,6 +1401,20 @@ simplify_stmt_for_jump_threading (gimple
return lookup_avail_expr (stmt, false);
}
+/* Valueize hook for gimple_fold_stmt_to_constant_1. */
+
+static tree
+dom_valueize (tree t)
+{
+ if (TREE_CODE (t) == SSA_NAME)
+ {
+ tree tem = SSA_NAME_VALUE (t);
+ if (tem)
+ return tem;
+ }
+ return t;
+}
+
/* Record into the equivalence tables any equivalences implied by
traversing edge E (which are cached in E->aux).
@@ -1428,7 +1442,6 @@ record_temporary_equivalences (edge e)
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);
@@ -1455,6 +1468,39 @@ record_temporary_equivalences (edge e)
}
}
}
+
+ /* If LHS is an SSA_NAME with a new equivalency then try if
+ stmts with uses of that LHS that dominate the edge destination
+ simplify and allow further equivalences to be recorded. */
+ if (lhs && TREE_CODE (lhs) == SSA_NAME)
+ {
+ gimple use_stmt;
+ imm_use_iterator iter;
+ 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 (e->dest == gimple_bb (use_stmt)
+ || !dominated_by_p (CDI_DOMINATORS,
+ e->dest, gimple_bb (use_stmt)))
+ continue;
+ tree lhs2 = gimple_get_lhs (use_stmt);
+ if (lhs2 && TREE_CODE (lhs2) == SSA_NAME)
+ {
+ tree res
+ = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize,
+ no_follow_ssa_edges);
+ if (res
+ && (TREE_CODE (res) == SSA_NAME
+ || is_gimple_min_invariant (res)))
+ record_equality (lhs2, res);
+ }
+ }
+ }
/* If we have 0 = COND or 1 = COND equivalences, record them
into our expression hash tables. */
