public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Richard Sandiford <richard.sandiford@linaro.org>
To: "Bin.Cheng" <amker.cheng@gmail.com>
Cc: "gcc-patches\@gcc.gnu.org" <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
Date: Wed, 24 May 2017 10:55:00 -0000	[thread overview]
Message-ID: <87a862zfrt.fsf@linaro.org> (raw)
In-Reply-To: <CAHFci2_EMsCfRvriHKb2BPeJaJVWX9Aoy8Co-kFh2N8=rB8zvQ@mail.gmail.com>	(Bin Cheng's message of "Wed, 24 May 2017 11:16:55 +0100")

"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?

> 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).

>> 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-24 10:54 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 [this message]
2017-05-25 15:16       ` Bin.Cheng
2017-05-26 11:43         ` Richard Biener
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=87a862zfrt.fsf@linaro.org \
    --to=richard.sandiford@linaro.org \
    --cc=amker.cheng@gmail.com \
    --cc=gcc-patches@gcc.gnu.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).