On Fri, 24 Apr 2015, Jeff Law wrote:
> On 02/17/2015 07:58 AM, Richard Biener wrote:
> [ Restarting a old thread... ]
>
> > On a closer look the record_const_or_copy_1 hunk is redundant
> > (record_equality is really a bit obfuscated...).
> Agreed. I'm not entirely sure how it got to this point.
>
> > And record_equality is where the SSA_NAME_VALUEs might end up
> > forming chains? At least because we might record a SSA_NAME_VALUE
> > for sth that might be the target of a SSA_NAME_VALUE, as in
> >
> > a_1 = b_2; SSA_NAME_VALUE (a_1) == b_2;
> > if (b_2 == i_3(D))
> > ... temporarily SSA_NAME_VALUE (b_2) == i_3(D)
> >
> > thus under if (b_2 == i_3(D)) SSA_NAME_VALUE (a_1) == b_2 and
> > SSA_NAME_VALUE (SSA_NAME_VALUE (a_1)) == i_3(D)? I guess we
> > can't easily avoid that because we don't keep track of a
> > reverse mapping (nor would we want to update that).
> Right. In general, the fact that we're in SSA form means that we ought not
> get loops in the SSA_NAME_VALUE chain since there's a single static assignment
> and we'll visit it once.
>
> That nice model breaks down in two ways. First we derive equivalences from
> equality conditions like you've shown above. Second, when threading we can
> thread through a loop latch and start reprocessing a block. The interaction
> between those two can result in loops in the value chain.
>
> What I'm hoping to do in GCC6 is eliminate all this stuff with a threader that
> is independent of the dominator walk (and optimizer). Instead of walking
> forward through the dominator tree recording key nuggets, then removing those
> nuggets as we pop back up the tree, we instead we start with the conditional
> and walk up the use-def chains, simplifying as we go, with the goal of
> simplifying to a constant, of course.
>
> You can see the beginnings of that with the FSM bits from Sebastian.
>
> Obviously until those bits are in place, we should try to clean up any warts
> in the current implementation.
>
> >
> > Btw, in record_equality, the == part of the <= check for the loop
> > depth will just randomly swap x and y while we should prefer
> > IL canonical order. If we can't rely on the input being in IL
> > canonical order we should prepend the whole function with
> >
> > if (tree_swap_operands_p (x, y, false))
> > std::swap (x, y);
> >
> > and change <= to < for the loop-depth check.
> Agreed. Makes perfect sense.
I'm now re-bootstrapping and testing the following.
Richard.
2015-04-27 Richard Biener <rguent...@suse.de>
* tree-ssa-dom.c (record_equivalences_from_phis): Valueize PHI arg.
(record_equivalences_from_stmt): Valueize rhs.
(record_equality): Canonicalize x and y order via
tree_swap_operands_p. Do not swap operands for same loop depth.
Index: gcc/tree-ssa-dom.c
===================================================================
*** gcc/tree-ssa-dom.c (revision 222360)
--- gcc/tree-ssa-dom.c (working copy)
*************** record_equivalences_from_phis (basic_blo
*** 1519,1524 ****
--- 1519,1531 ----
if (lhs == t)
continue;
+ /* Valueize t. */
+ if (TREE_CODE (t) == SSA_NAME)
+ {
+ tree tmp = SSA_NAME_VALUE (t);
+ t = tmp ? tmp : t;
+ }
+
/* If we have not processed an alternative yet, then set
RHS to this alternative. */
if (rhs == NULL)
*************** record_equality (tree x, tree y)
*** 1752,1757 ****
--- 1759,1767 ----
{
tree prev_x = NULL, prev_y = NULL;
+ if (tree_swap_operands_p (x, y, false))
+ std::swap (x, y);
+
if (TREE_CODE (x) == SSA_NAME)
prev_x = SSA_NAME_VALUE (x);
if (TREE_CODE (y) == SSA_NAME)
*************** record_equality (tree x, tree y)
*** 1766,1772 ****
else if (is_gimple_min_invariant (x)
/* ??? When threading over backedges the following is important
for correctness. See PR61757. */
! || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
prev_x = x, x = y, y = prev_x, prev_x = prev_y;
else if (prev_x && is_gimple_min_invariant (prev_x))
x = y, y = prev_x, prev_x = prev_y;
--- 1776,1782 ----
else if (is_gimple_min_invariant (x)
/* ??? When threading over backedges the following is important
for correctness. See PR61757. */
! || (loop_depth_of_name (x) < loop_depth_of_name (y)))
prev_x = x, x = y, y = prev_x, prev_x = prev_y;
else if (prev_x && is_gimple_min_invariant (prev_x))
x = y, y = prev_x, prev_x = prev_y;
*************** record_equivalences_from_stmt (gimple st
*** 2128,2145 ****
if (may_optimize_p
&& (TREE_CODE (rhs) == SSA_NAME
|| is_gimple_min_invariant (rhs)))
! {
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "==== ASGN ");
! print_generic_expr (dump_file, lhs, 0);
! fprintf (dump_file, " = ");
! print_generic_expr (dump_file, rhs, 0);
! fprintf (dump_file, "\n");
! }
! set_ssa_name_value (lhs, rhs);
! }
}
/* Make sure we can propagate &x + CST. */
--- 2138,2162 ----
if (may_optimize_p
&& (TREE_CODE (rhs) == SSA_NAME
|| is_gimple_min_invariant (rhs)))
! {
! /* Valueize rhs. */
! if (TREE_CODE (rhs) == SSA_NAME)
! {
! tree tmp = SSA_NAME_VALUE (rhs);
! rhs = tmp ? tmp : rhs;
! }
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "==== ASGN ");
! print_generic_expr (dump_file, lhs, 0);
! fprintf (dump_file, " = ");
! print_generic_expr (dump_file, rhs, 0);
! fprintf (dump_file, "\n");
! }
!
! set_ssa_name_value (lhs, rhs);
! }
}
/* Make sure we can propagate &x + CST. */
