public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Richard Biener <richard.guenther@gmail.com>
To: "Bin.Cheng" <amker.cheng@gmail.com>
Cc: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,
		Richard Sandiford <richard.sandiford@linaro.org>
Subject: Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
Date: Fri, 26 May 2017 11:43:00 -0000	[thread overview]
Message-ID: <CAFiYyc247XgEgN8U9fkAMCmRTBvwkTxQ=N3ODwi9WongOC3+8g@mail.gmail.com> (raw)
In-Reply-To: <CAHFci29-ab_Ov8sbx+OHdoQRRO7Q5QbszbJ1a+7RzdNojksY4g@mail.gmail.com>

On Thu, May 25, 2017 at 5:15 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Wed, May 24, 2017 at 11:54 AM, Richard Sandiford
> <richard.sandiford@linaro.org> wrote:
>> "Bin.Cheng" <amker.cheng@gmail.com> writes:
>>> On Tue, May 23, 2017 at 6:53 PM, Richard Sandiford
>>> <richard.sandiford@linaro.org> wrote:
>>>> AIUI, the reason the old code mishandled negative steps was that the
>>>> associated segment lengths were stored as sizetype and so looked like
>>>> big unsigned values.  Those values therefore satisfied tree_fits_uhwi_p
>>>> even though they were semantically negative.  Is that right?
>>> Yes, and the undesired wrapping behavior when such large unsigned hwi
>>> is involved in computation.  But I think there are possible leaks in
>>> the code even after this patch, as embedded below.
>>>>
>>>> Assuming yes, and quoting the change as a context diff...
>>>>
>>>>> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
>>>>> index a5f8c1c..f0799d9 100644
>>>>> *** a/gcc/tree-data-ref.c
>>>>> --- b/gcc/tree-data-ref.c
>>>>> ***************
>>>>> *** 1259,1264 ****
>>>>> --- 1259,1273 ----
>>>>>             != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node))
>>>>>           continue;
>>>>>
>>>>> +       bool neg_step
>>>>> +         = (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) < 0);
>>>>> +
>>>>> +       /* DR_A1 and DR_A2 must have the same step if it's negative.  */
>>>>> +       if (neg_step
>>>>> +           && tree_int_cst_compare (DR_STEP (dr_a1->dr),
>>>>> +                                    DR_STEP (dr_a2->dr)) != 0)
>>>>> +         continue;
>>>>> +
>>>>
>>>> [Why do they need to be the same step?]
>>> There are two reasons.  First is to simplify diff computation between
>>> dr_a1 and dr_a2, otherwise we need to adjust diff for negative steps.
>>
>> What kind of adjustment would be needed?  Could you give an example?
> I handled negative step in updated patch by adjusting diff according
> to access size of references.

It's quite hard to follow.  Isn't it more correct to always extend seg-len
by the access size?  And only consider neg_step when deciding which
pair to keep/extend (which DR_BASE_ADDRESS is eventually used)?

>>
>>> And wrapping behavior needs to be handled when adjusting diff with
>>> steps.  The second reason is not fully handled in this patch.  We now
>>> only set merged segment length to MAX only when both dr_a1->seg_len
>>> and dr_a2->seg_len are constant, as below:
>>> +          if (tree_fits_uhwi_p (dr_a1->seg_len)
>>> +              && tree_fits_uhwi_p (dr_a2->seg_len))
>>> +            new_seg_len
>>> +              = size_int (MAX (tree_to_uhwi (dr_a1->seg_len),
>>> +                       diff + tree_to_uhwi (dr_a2->seg_len)));
>>> +          else
>>> +            new_seg_len
>>> +              = size_binop (PLUS_EXPR, dr_a2->seg_len, size_int (diff));
>>> In fact, we should do this for else branch too.  with different steps,
>>> it is still possible that dr_a1-seg_len > dr_a2->seg_len + diff.  Here
>>> I only restrict it to negative DR_STEP.  Patch updated with
>>> explanation in comment.
>>>>
>>>>>         /* Make sure dr_a1 starts left of dr_a2.  */
>>>>>         if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
>>>>>           std::swap (*dr_a1, *dr_a2);
>>>>> ***************
>>>>> *** 1266,1325 ****
>>>>>         bool do_remove = false;
>>>>>         unsigned HOST_WIDE_INT diff
>>>>>           = (tree_to_shwi (DR_INIT (dr_a2->dr))
>>>>> !                - tree_to_shwi (DR_INIT (dr_a1->dr)));
>>>>>
>>>>> !       /* If the left segment does not extend beyond the start of the
>>>>> !          right segment the new segment length is that of the right
>>>>> !          plus the segment distance.  */
>>>>> !       if (tree_fits_uhwi_p (dr_a1->seg_len)
>>>>> !           && compare_tree_int (dr_a1->seg_len, diff) <= 0)
>>>>>           {
>>>>> !           dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
>>>>> !                                        size_int (diff));
>>>>> !           do_remove = true;
>>>>>           }
>>>>> !       /* Generally the new segment length is the maximum of the
>>>>> !          left segment size and the right segment size plus the distance.
>>>>> !          ???  We can also build tree MAX_EXPR here but it's not clear this
>>>>> !          is profitable.  */
>>>>> !       else if (tree_fits_uhwi_p (dr_a1->seg_len)
>>>>> !                && tree_fits_uhwi_p (dr_a2->seg_len))
>>>>> !         {
>>>>> !           unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
>>>>> !           unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
>>>>> !           dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
>>>>> !           do_remove = true;
>>>>> !         }
>>>>> !       /* Now we check if the following condition is satisfied:
>>>>>
>>>>> !          DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
>>>>>
>>>>> !          where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
>>>>> !          SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
>>>>> !          have to make a best estimation.  We can get the minimum value
>>>>> !          of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
>>>>> !          then either of the following two conditions can guarantee the
>>>>> !          one above:
>>>>>
>>>>> !          1: DIFF <= MIN_SEG_LEN_B
>>>>> !          2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
>>>>> !       else
>>>>>           {
>>>>> !           unsigned HOST_WIDE_INT min_seg_len_b
>>>>> !             = (tree_fits_uhwi_p (dr_b1->seg_len)
>>>>> !                ? tree_to_uhwi (dr_b1->seg_len)
>>>>> !                : factor);
>>>>>
>>>>>             if (diff <= min_seg_len_b
>>>>>                 || (tree_fits_uhwi_p (dr_a1->seg_len)
>>>>> !                   && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
>>>>>               {
>>>>> !               dr_a1->seg_len = size_binop (PLUS_EXPR,
>>>>> !                                            dr_a2->seg_len, size_int (diff));
>>>>>                 do_remove = true;
>>>>>               }
>>>>>           }
>>>>>
>>>>>         if (do_remove)
>>>>>           {
>>>>>             if (dump_enabled_p ())
>>>>> --- 1275,1375 ----
>>>>>         bool do_remove = false;
>>>>>         unsigned HOST_WIDE_INT diff
>>>>>           = (tree_to_shwi (DR_INIT (dr_a2->dr))
>>>>> !            - tree_to_shwi (DR_INIT (dr_a1->dr)));
>>>>> !       tree new_seg_len;
>>>>> !       unsigned HOST_WIDE_INT min_seg_len_b;
>>>>>
>>>>> !       if (tree_fits_uhwi_p (dr_b1->seg_len))
>>>>>           {
>>>>> !           min_seg_len_b = tree_to_uhwi (dr_b1->seg_len);
>>>>> !           if (tree_int_cst_sign_bit (dr_b1->seg_len))
>>>>> !             min_seg_len_b = 0 - min_seg_len_b;
>>>>>           }
>>>>> !       else
>>>>> !         min_seg_len_b = factor;
>>>>
>>>> ...I'm not sure how safe this or the later neg_step handling is
>>>> for 16-bit and 32-bit sizetypes.  It might be better to use wide_int
>>> I think it could be a problem in case sizetype is smaller than
>>> unsigned_type_for(ptr).
>>
>> But I think it would a problem even for "normal" 32-bit and 16-bit
>> targets, because you're doing uhwi (i.e. 64-bit) negation on things that
>> come from 32-bit and 16-bit unsigned values.  E.g. a segment length of
>> -32 on a 32-bit target would be 0xffffffe0.  If you read that as a uhwi
>> and negate it, you get 0xffffffff00000020 rather than 32.
>>
>> Using wide_ints would avoid that.  I don't think the existing code
>> needed it (because the existing code didn't handle negative steps
>> properly at all).
> Right, patch updated using wide_int to compare diff and compute merged
> segment length.
> Bootstrap and test on x86_64 and AArch64.
>
> Thanks,
> bin
>>
>>>> instead, so that all arithmetic and comparisons happen in the precision
>>>> of sizetype.
>>> I was trying to make minimal refactoring for fixing the negative step
>>> issue.  Also I guess your SVE patches will rewrite this part entirely?
>>
>> Not sure TBH :-)  I'll have to see how it works out when I merge it in.
>>
>> Thanks,
>> Richard

  reply	other threads:[~2017-05-26 11:39 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-05-23 16:23 Bin Cheng
2017-05-23 17:56 ` Richard Sandiford
2017-05-24 10:54   ` Bin.Cheng
2017-05-24 10:55     ` Richard Sandiford
2017-05-25 15:16       ` Bin.Cheng
2017-05-26 11:43         ` Richard Biener [this message]
2017-05-26 12:01           ` Bin.Cheng
2017-05-26 12:31             ` Richard Biener

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAFiYyc247XgEgN8U9fkAMCmRTBvwkTxQ=N3ODwi9WongOC3+8g@mail.gmail.com' \
    --to=richard.guenther@gmail.com \
    --cc=amker.cheng@gmail.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=richard.sandiford@linaro.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).