Re: [PATCH] A jump threading opportunity for condition branch

[Richard Biener <rguenther@suse.de>]

On May 29, 2019 10:12:31 PM GMT+02:00, Jeff Law <law@redhat.com> wrote:
>On 5/23/19 6:05 AM, Jiufu Guo wrote:
>> Hi,
>> 
>> Richard Biener <rguenther@suse.de> writes:
>> 
>>> On Tue, 21 May 2019, Jiufu Guo wrote:
>>>
>
>>>>  
>>>> +/* Return true if PHI's INDEX-th incoming value is a CMP, and the
>CMP is
>>>> +   defined in the incoming basic block. Otherwise return false. 
>*/
>>>> +static bool
>>>> +cmp_from_unconditional_block (gphi *phi, int index)
>>>> +{
>>>> +  tree value = gimple_phi_arg_def (phi, index);
>>>> +  if (!(TREE_CODE (value) == SSA_NAME && has_single_use (value)))
>>>> +    return false;
>>> Not sure why we should reject a constant here but I guess we
>>> expect it to find a simplified condition anyways ;)
>>>
>> Const could be accepted here, like "# t_9 = PHI <5(3), t_17(4)>". I
>> found this case is already handled by other jump-threading code, like
>> 'ethread' pass.
>Right.  There's no need to handle constants here.  They'll result in
>trivially discoverable jump threading opportunities.
>
>>>> +  /* Check if phi's incoming value is defined in the incoming
>basic_block.  */
>>>> +  edge e = gimple_phi_arg_edge (phi, index);
>>>> +  if (def->bb != e->src)
>>>> +    return false;
>>> why does this matter?
>>>
>> Through preparing pathes and duplicating block, this transform can
>also
>> help to combine a cmp in previous block and a gcond in current block.
>> "if (def->bb != e->src)" make sure the cmp is define in the incoming
>> block of the current; and then combining "cmp with gcond" is safe. 
>If
>> the cmp is defined far from the incoming block, it would be hard to
>> achieve the combining, and the transform may not needed.
>I don't think it's strictly needed in the long term and could be
>addressed in a follow-up if we can find cases where it helps.  I think
>we'd just need to double check insertion of the new conditional branch
>to relax this if we cared.
>
>However, I would expect sinking to have done is job here and would be
>surprised if trying to handle this actually improved any real world
>code.
>> 
>>>> +
>>>> +  if (!single_succ_p (def->bb))
>>>> +    return false;
>>> Or this?  The actual threading will ensure this will hold true.
>>>
>> Yes, other thread code check this and ensure it to be true, like
>> function thread_through_normal_block. Since this new function is
>invoked
>> outside thread_through_normal_block, so, checking single_succ_p is
>also
>> needed for this case.
>Agreed that it's needed.  Consider if the source block has multiple
>successors.  Where do we insert the copy of the conditional branch?

We're duplicating its block? That is, we are isolating a path into a conditional - that's always possible? I wanted to make sure that when threading threads through a conditional in the block with the compare we'd add the extra tail duplication? AFAIK we're still looking at unmodified CFG here?

>
>>>> +{
>>>> +  gimple *gs = last_and_only_stmt (bb);
>>>> +  if (gs == NULL)
>>>> +    return false;
>>>> +
>>>> +  if (gimple_code (gs) != GIMPLE_COND)
>>>> +    return false;
>>>> +
>>>> +  tree cond = gimple_cond_lhs (gs);
>>>> +
>>>> +  if (TREE_CODE (cond) != SSA_NAME)
>>>> +    return false;
>>> space after if( too much vertical space in this function
>>> for my taste btw.
>> Will update this.
>>> For the forwarding to work we want a NE_EXPR or EQ_EXPR
>>> as gimple_cond_code and integer_one_p or integer_zero_p
>>> gimple_cond_rhs.
>> Right, checking those would be more safe.  Since no issue found,
>during
>> bootstrap and regression tests, so I did not add these checking.  I
>will
>> add this checking.
>Definitely want to verify that we're dealing with an equality test
>against 0/1.
>
>Jeff