On 11/12/13 2:03 PM, Tom de Vries wrote:
> On 11-11-13 14:17, Richard Biener wrote:
>> On Mon, 11 Nov 2013, Tom de Vries wrote:
>>
>>> On 11/11/13 10:50, Richard Biener wrote:
>>>> On Sat, 9 Nov 2013, Tom de Vries wrote:
>>>>> Bootstrapped and regtested on x86_64.
>>>>>
>>>>> OK for trunk?
>>>>
>>>> Comments inline
>>>>
>>>>
>>>> diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
>>>> index 98b5882..43516a7 100644
>>>> --- a/gcc/tree-ssa-tail-merge.c
>>>> +++ b/gcc/tree-ssa-tail-merge.c
>>>> @@ -1173,8 +1173,47 @@ gimple_equal_p (same_succ same_succ, gimple
>>>> s1, gimple s2)
>>>> lhs2 = gimple_get_lhs (s2);
>>>> if (TREE_CODE (lhs1) != SSA_NAME
>>>> && TREE_CODE (lhs2) != SSA_NAME)
>>>> - return (vn_valueize (gimple_vdef (s1))
>>>> - == vn_valueize (gimple_vdef (s2)));
>>>> + {
>>>> + /* If the vdef is the same, it's the same statement. */
>>>> + if (vn_valueize (gimple_vdef (s1))
>>>> + == vn_valueize (gimple_vdef (s2)))
>>>> + return true;
>>>> +
>>>> + /* If the vdef is not the same but the vuse is the same, it's
>>>> not the
>>>> + same stmt. */
>>>> + if (vn_valueize (gimple_vuse (s1))
>>>> + == vn_valueize (gimple_vuse (s2)))
>>>> + return false;
>>>>
>>>
>>> Richard,
>>>
>>>> What's the logic behind this?
>>>> We want to use VN to get more "positive"
>>>> results
>>>
>>> We can use it to get both positive and negative results faster.
>>
>> I can get a negative result for free: "false" ;)
>>
>
> Richard,
>
> Indeed. But perhaps we could regard the question at hand from the
> perspective of both compilation effect and compilation speed ;)
>
>> VN proves equivalency it doesn't prove non-equivalency - that's
>> simply its conservative fallback.
>>
>
> Of course.
>
>>>> - doing a negative early out looks suspicious to me ...
>>>>
>>>
>>> If the vdefs are the same, the VN has concluded that the statements
>>> are the
>>> same. We have a positive early out.
>>>
>>> If the vdefs are not the same, the VN has concluded that the
>>> statements are
>>> different. But if the vuses are the same, the VN has concluded that the
>>> statements are different because of structural difference. Which
>>> means there's
>>> no sense in us repeating the structural comparison. We have a
>>> negative early out.
>>
>> Well, see above - it merely failed to prove equivalency, it didn't
>> actually conclude they are different.
>>
>
> You're right, sloppy formulation on my part.
>
> My question is, if VN has tried to prove equality of vdefs, and failed,
> in what scenario could a structural comparison still prove them equal?
>
> In case the vuses are not proven equal, there's an obvious reason why
> the vdefs are not proven equal, and structural comparison might indeed
> prove them equal.
>
> But if the vuses are proven equal, that's not the reason why the vdefs
> are not proven equal. In which case it's hard for me to understand how a
> trivial structural check would beat VN.
>
> I've browsed the VN code a bit and tried to construct examples where
> structural comparison beats VN, but did not manage.
>
> I've also done a non-bootstrap build with attached patch, and a complete
> testrun, and was not able to trigger the assert.
>
> So if you have any hunch about such a scenario, please let me know.
I don't - just relying on the value-number for virtual operands always
makes me nervous.
I'm fine with the early out, it just looks odd to me (the compile-time
effect should be minimal).
Richard.
> Thanks,
> - Tom
>
>>> If the vdefs are not the same, the VN has concluded that the
>>> statements are
>>> different. But if the vuses are different, the VN may have concluded
>>> that the
>>> statements are different because of the different vuses. So it still
>>> makes sense
>>> to try structural comparison.
>>>
>>>> + /* If the vdef is not the same and the vuse is not the same,
>>>> it might be
>>>> + same stmt. */
>>>> +
>>>> + /* Test for structural equality. */
>>>> + if (gimple_assign_rhs_code (s1) != gimple_assign_rhs_code (s1)
>>>>
>>>> s2
>>>>
>>>> + || (gimple_assign_nontemporal_move_p (s1)
>>>> + != gimple_assign_nontemporal_move_p (s2)))
>>>>
>>>> I don't think we should care (it'll be false - a later pass sets it,
>>>> it's an optimization hint, not a correctness issue). More interesting
>>>> would be to assert that has_volatile_ops is the same if the operands
>>>> turned out to be the same.
>>>>
>>>
>>> OK.
>>>
>>>> + return false;
>>>> +
>>>> + if (!operand_equal_p (lhs1, lhs2, 0))
>>>> + return false;
>>>> +
>>>> + t1 = gimple_assign_rhs1 (s1);
>>>> + t2 = gimple_assign_rhs1 (s2);
>>>> + if (!gimple_operand_equal_value_p (t1, t2))
>>>> + return false;
>>>> +
>>>> + t1 = gimple_assign_rhs2 (s1);
>>>> + t2 = gimple_assign_rhs2 (s2);
>>>> + if (!gimple_operand_equal_value_p (t1, t2))
>>>> + return false;
>>>> +
>>>> + t1 = gimple_assign_rhs3 (s1);
>>>> + t2 = gimple_assign_rhs3 (s2);
>>>> + if (!gimple_operand_equal_value_p (t1, t2))
>>>> + return false;
>>>>
>>>> for (i = 1; i < gimple_num_ops (s1); ++i)
>>>> t1 = gimple_op (s1, i);
>>>> ...
>>>>
>>>> but I think you should only compare rhs1 and thus only handle
>>>> GIMPLE_ASSIGN_SINGLEs this way - the others have a SSA name
>>>> lhs.
>>>>
>>>
>>> I see.
>>>
>>>> That makes the whole thing just
>>>>
>>>> if (TREE_CODE (lhs1) != SSA_NAME
>>>> && TREE_CODE (lhs2) != SSA_NAME)
>>>> {
>>>> if (vn_valueize (gimple_vdef (s1))
>>>> == vn_valueize (gimple_vdef (s2)))
>>>> return true;
>>>> return operand_equal_p (lhs1, lhs2, 0)
>>>> && gimple_operand_equal_value_p (gimple_assign_rhs1
>>>> (s1),
>>>> gimple_assign_rhs2
>>>> (s2));
>>>> }
>>>>
>>>> Ok with doing it this way.
>>>
>>> I'll retest and checkin like this, unless you agree about the early
>>> out, which I
>>> still think is a good idea, although the structural test is now much
>>> smaller.
>>
>> I think the early out is premature.
>>
>> Richard.
>>
>
