Re: [PATCH PR69489/01]Improve tree ifcvt by storing/tracking DR against its innermost loop bahavior if possible

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Apr 4, 2016 at 4:14 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Mon, Apr 4, 2016 at 2:07 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Thu, Mar 31, 2016 at 6:43 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> On Tue, Mar 29, 2016 at 9:37 AM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>> On Mon, Mar 28, 2016 at 9:57 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>> Sorry, Should have replied to gcc-patches list.
>>>>>
>>>>> Thanks,
>>>>> bin
>>>>>
>>>>> ---------- Forwarded message ----------
>>>>> From: "Bin.Cheng" <amker.cheng@gmail.com>
>>>>> Date: Tue, 29 Mar 2016 03:55:04 +0800
>>>>> Subject: Re: [PATCH PR69489/01]Improve tree ifcvt by storing/tracking
>>>>> DR against its innermost loop bahavior if possible
>>>>> To: Richard Biener <richard.guenther@gmail.com>
>>>>>
>>>>> On 3/17/16, Richard Biener <richard.guenther@gmail.com> wrote:
>>>>>> On Wed, Mar 16, 2016 at 5:17 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>>>>>> On Wed, Mar 16, 2016 at 12:20 PM, Richard Biener
>>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>
>>>>>> It is an alternative to adding a hook to get_references_in_stmt and
>>>>>> probably "easier".
>>>>>>
>>>>>>>>
>>>>>>>> Index: tree-if-conv.c
>>>>>>>> ===================================================================
>>>>>>>> --- tree-if-conv.c      (revision 234215)
>>>>>>>> +++ tree-if-conv.c      (working copy)
>>>>>>>> @@ -1235,6 +1220,38 @@ if_convertible_loop_p_1 (struct loop *lo
>>>>>>>>
>>>>>>>>    for (i = 0; refs->iterate (i, &dr); i++)
>>>>>>>>      {
>>>>>>>> +      tree *refp = &DR_REF (dr);
>>>>>>>> +      while ((TREE_CODE (*refp) == COMPONENT_REF
>>>>>>>> +             && TREE_OPERAND (*refp, 2) == NULL_TREE)
>>>>>>>> +            || TREE_CODE (*refp) == IMAGPART_EXPR
>>>>>>>> +            || TREE_CODE (*refp) == REALPART_EXPR)
>>>>>>>> +       refp = &TREE_OPERAND (*refp, 0);
>>>>>>>> +      if (refp != &DR_REF (dr))
>>>>>>>> +       {
>>>>>>>> +         tree saved_base = *refp;
>>>>>>>> +         *refp = integer_zero_node;
>>>>>>>> +
>>>>>>>> +         if (DR_INIT (dr))
>>>>>>>> +           {
>>>>>>>> +             tree poffset;
>>>>>>>> +             int punsignedp, preversep, pvolatilep;
>>>>>>>> +             machine_mode pmode;
>>>>>>>> +             HOST_WIDE_INT pbitsize, pbitpos;
>>>>>>>> +             get_inner_reference (DR_REF (dr), &pbitsize, &pbitpos,
>>>>>>>> &poffset,
>>>>>>>> +                                  &pmode, &punsignedp, &preversep,
>>>>>>>> &pvolatilep,
>>>>>>>> +                                  false);
>>>>>>>> +             gcc_assert (poffset == NULL_TREE);
>>>>>>>> +
>>>>>>>> +             DR_INIT (dr)
>>>>>>>> +               = wide_int_to_tree (ssizetype,
>>>>>>>> +                                   wi::sub (DR_INIT (dr),
>>>>>>>> +                                            pbitpos / BITS_PER_UNIT));
>>>>>>>> +           }
>>>>>>>> +
>>>>>>>> +         *refp = saved_base;
>>>>>>>> +         DR_REF (dr) = *refp;
>>>>>>>> +       }
>>>>>>> Looks to me the code is trying to resolve difference between two (or
>>>>>>> more) component references, which is DR_INIT in the code.  But DR_INIT
>>>>>>> is not the only thing needs to be handled.  For a structure containing
>>>>>>> two sub-arrays, DR_OFFSET may be different too.
>>>>>>
>>>>>> Yes, but we can't say that if
>>>>>>
>>>>>>   a->a[i]
>>>>>>
>>>>>> doesn't trap that then
>>>>>>
>>>>>>   a->b[i]
>>>>>>
>>>>>> doesn't trap either.  We can only "strip" outermost
>>>>>> non-variable-offset components.
>>>>>>
>>>>>> But maybe I'm missing what example you are thinking of.
>>>>> Hmm, this was the case I meant.  What I don't understand is current
>>>>> code logic does infer trap information for a.b[i] from a.a[i].  Given
>>>>> below example:
>>>>> struct str
>>>>> {
>>>>>   int a[10];
>>>>>   int b[20];
>>>>>   char c;
>>>>> };
>>>>>
>>>>> void bar (struct str *);
>>>>> int foo (int x, int n)
>>>>> {
>>>>>   int i;
>>>>>   struct str s;
>>>>>   bar (&s);
>>>>>   for (i = 0; i < n; i++)
>>>>>     {
>>>>>       s.a[i] = s.b[i];
>>>>>       if (x > i)
>>>>>         s.b[i] = 0;
>>>>>     }
>>>>>   bar (&s);
>>>>>   return 0;
>>>>> }
>>>>> The loop is convertible because of below code in function
>>>>> ifcvt_memrefs_wont_trap:
>>>>>
>>>>>   /* If a is unconditionally accessed then ... */
>>>>>   if (DR_RW_UNCONDITIONALLY (*master_dr))
>>>>>     {
>>>>>       /* an unconditional read won't trap.  */
>>>>>       if (DR_IS_READ (a))
>>>>>         return true;
>>>>>
>>>>>       /* an unconditionaly write won't trap if the base is written
>>>>>          to unconditionally.  */
>>>>>       if (base_master_dr
>>>>>           && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
>>>>>         return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
>>>>>       else
>>>>>         {
>>>>>           /* or the base is know to be not readonly.  */
>>>>>           tree base_tree = get_base_address (DR_REF (a));
>>>>>           if (DECL_P (base_tree)
>>>>>               && decl_binds_to_current_def_p (base_tree)
>>>>>               && ! TREE_READONLY (base_tree))
>>>>>             return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
>>>>>         }
>>>>>     }
>>>>> It is the main object '&s' that is recorded in base_master_dr, so
>>>>> s.b[i] is considered not trap.  Even it's not, I suppose
>>>>> get_base_address will give same result?
>>>>
>>>> Well, for this case it sees that s.b[i] is read from so it can't be an
>>>> out-of-bound
>>>> access.  And s.a[i] is written to unconditionally so 's' cannot be a
>>>> readonly object.
>>>> With both pieces of information we can conclude that s.b[i] = 0 doesn't trap.
>>>
>>> Hi Richard,
>>> Attachment is the updated patch.  I made below changes wrto your
>>> review comments:
>>> 1) Moved hash class for innermost loop behavior from tree-data-ref.h
>>> to tree-if-conv.c.
>>>     I also removed check on innermost_loop_behavior.aligned_to which
>>> seems redundant to me because it's computed from offset and we have
>>> already checked equality for offset.
>>> 2) Replaced ref_DR_map with new map innermost_DR_map.
>>> 3) Post-processed DR in if_convertible_loop_p_1 for compound reference
>>> or references don't have innermost behavior.  This cleans up following
>>> code using DR information.
>>> 4) Added a vectorization test for PR56625.
>>>
>>> I didn't incorporate your proposed code because I think it handles
>>> COMPONENT_REF of structure array like struct_arr[i].x/struct_arr[i].y.
>>
>> But the previous code already handled it, so not handling it would be
>> a regression.
>> Note that I think your patch will handle it as well given you hash innermost
>> behavior.
> If I understand correctly, your code is more precise handling
> component reference by stripping const offset from innermost loop
> behavior.  Currently tree if-conv just strips component ref for
> structure field away.  Yes my patch can handle the case, but that's
> done by falling back to the reference itself (the existing code
> logic), rather than tunning innermost loop behavior as you suggested:

Ah, indeed.

> +          while (TREE_CODE (ref) == COMPONENT_REF
> +             || TREE_CODE (ref) == IMAGPART_EXPR
> +             || TREE_CODE (ref) == REALPART_EXPR)
> +        ref = TREE_OPERAND (ref, 0);
> +
> +          DR_BASE_ADDRESS (dr) = ref;
> +          DR_OFFSET (dr) = NULL;
> +          DR_INIT (dr) = NULL;
> +          DR_STEP (dr) = NULL;
> +          DR_ALIGNED_TO (dr) = NULL;
>
> I think innermost loop behavior is unnecessary here for component
> refs, so is there an example showing possible exception?

Well, we don't need the outer component refs but DR analyze included
them in its analysis (and thus DR_INIT will differ).  For cases DR analyze
failed on that doesn't matter of course.

> I will re-base/apply the patch after entering Stage1.

Thanks,
Richard.

> Thanks,
> bin
>>
>>> Looks to me it is another ifcvt opportunity different from PR69489.
>>> Anyway, fix is easy, I can send another patch in GCC7.
>>>
>>> Bootstrap and test on x86_64/AArch64, so any comments on this version?
>>
>> Looks good to me.
>>
>> Richard.
>>