| Message ID | CAHFci29-ab_Ov8sbx+OHdoQRRO7Q5QbszbJ1a+7RzdNojksY4g@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
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
On Fri, May 26, 2017 at 12:39 PM, Richard Biener <richard.guenther@gmail.com> wrote: > 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 Extending seg-len unconditionally by access size is more conservative and safer, but I tried to keep alias pair merging precise by not using unnecessary approximation. Using approximation could be simpler in terms of LoC, but it also causes confusion for others to understand why/when we are merging. > by the access size? And only consider neg_step when deciding which > pair to keep/extend (which DR_BASE_ADDRESS is eventually used)? Things like: while pair to keep/extend; how long seg_len should be extended; the condition when pairs should be considered for merging; they are all depends on neg_step or not. It's really hard to abstract code for pos_step and neg_step cases, so I took the other way around, simply separate code according to step's sign. I think the code is more straightforward, and easier for further changes in this way. Thanks, bin > >>> >>>> 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
On Fri, May 26, 2017 at 1:59 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Fri, May 26, 2017 at 12:39 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> 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 > Extending seg-len unconditionally by access size is more conservative > and safer, but I tried to keep alias pair merging precise by not using > unnecessary approximation. Using approximation could be simpler in > terms of LoC, but it also causes confusion for others to understand > why/when we are merging. > >> by the access size? And only consider neg_step when deciding which >> pair to keep/extend (which DR_BASE_ADDRESS is eventually used)? > Things like: while pair to keep/extend; how long seg_len should be > extended; the condition when pairs should be considered for merging; > they are all depends on neg_step or not. It's really hard to abstract > code for pos_step and neg_step cases, so I took the other way around, > simply separate code according to step's sign. I think the code is > more straightforward, and easier for further changes in this way. Ok, I'll take your word for it ;) Patch is ok. Thanks, Richard. > Thanks, > bin >> >>>> >>>>> 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
diff --git a/gcc/testsuite/gcc.dg/vect/pr80815-1.c b/gcc/testsuite/gcc.dg/vect/pr80815-1.c new file mode 100644 index 0000000..98c06c0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/pr80815-1.c @@ -0,0 +1,38 @@ +/* { dg-require-effective-target vect_int } */ + +#include "tree-vect.h" +int arr[2048]; + +__attribute__ ((noinline)) int +foo (int *a, int *b) +{ + int i; + int *a1 = a; + int *a0 = a1 - 512; + for (i = 0; i < 500; i++) + { + *b = *a0 + *a1; + b++; + a0--; + a1--; + } + return 0; +} + +int main (void) +{ + int *a = &arr[1027]; + int *b = &arr[1024]; + + int i; + for (i = 0; i < 2048; i++) + arr[i] = i; + + foo (a, b); + + if (arr[1026] != 2053 || arr[1027] != 2054) + abort (); + + return 0; +} + diff --git a/gcc/testsuite/gcc.dg/vect/pr80815-2.c b/gcc/testsuite/gcc.dg/vect/pr80815-2.c new file mode 100644 index 0000000..83557da --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/pr80815-2.c @@ -0,0 +1,46 @@ +/* { dg-require-effective-target vect_int } */ + +#include "tree-vect.h" +int arr[2048]; +int res[100] = { 13198, 13224, 12735, 12760, 12270, 12294, + 11803, 11826, 11334, 11356, 10863, 10884, + 10390, 10410, 9915, 9934, 9438, 9456, + 8959, 8976, 8478, 8494, 7995, 8010, + 7510, 7524, 7023, 7036, 6534, 6546, + 6043, 6054, 5550, 5560, 5055, 5064, + 4558, 4566, 4059, 4066, 3558, 3564, + 3055, 3060, 2550, 2554, 2043, 0}; + +__attribute__ ((noinline)) int +foo (int *a, int *b) +{ + int i; + int *a1 = a; + int *a0 = a1 - 512; + for (i = 0; i < 50; i++) + { + *b = *a0 + *a1; + b--; + a0--; + a1--; + } + return 0; +} + +int main (void) +{ + int *a = &arr[1024]; + int *b = &arr[1022]; + + int i; + for (i = 0; i < 2048; i++) + arr[i] = i; + + foo (a, b); + + for (i = 973; i < 1020; i++) + if (arr[i] != res[i - 973]) + abort (); + + return 0; +} diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index a5f8c1c..1a28000 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1259,63 +1259,115 @@ prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs, != 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); + + /* We need to compute merged segment length at compilation time for + dr_a1 and dr_a2, which is impossible if either one has non-const + segment length. */ + if ((!tree_fits_uhwi_p (dr_a1->seg_len) + || !tree_fits_uhwi_p (dr_a2->seg_len)) + && tree_int_cst_compare (DR_STEP (dr_a1->dr), + DR_STEP (dr_a2->dr)) != 0) + continue; + /* 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); 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)) + wide_int diff = wi::sub (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)); + wide_int min_seg_len_b; + tree new_seg_len; + + if (tree_fits_uhwi_p (dr_b1->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; + min_seg_len_b = dr_b1->seg_len; + if (tree_int_cst_sign_bit (dr_b1->seg_len)) + min_seg_len_b = wi::neg (min_seg_len_b); } - /* Now we check if the following condition is satisfied: + else + min_seg_len_b = wi::uhwi (factor, TYPE_PRECISION (sizetype)); + + /* Now we try to merge alias check dr_a1 & dr_b and dr_a2 & dr_b. + + Case A: + 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 + Because DIFF - SEGMENT_LENGTH_A is done in sizetype, we need + to take care of wrapping behavior in it. - DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B + Case B: + 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. The condition is like: - 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: + DIFF >= SEGMENT_LENGTH_A ;SEGMENT_LENGTH_A is a constant. - 1: DIFF <= MIN_SEG_LEN_B - 2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B */ + Note 1: Case A.2 and B combined together effectively merges every + dr_a1 & dr_b and dr_a2 & dr_b when SEGMENT_LENGTH_A is const. + + Note 2: Above description is based on positive DR_STEP, we need to + take care of negative DR_STEP for wrapping behavior. See PR80815 + for more information. */ + if (neg_step) + { + /* Adjust diff according to access size of both references. */ + tree size_a1 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a1->dr))); + tree size_a2 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a2->dr))); + diff = wi::add (diff, wi::sub (size_a2, size_a1)); + /* Case A.1. */ + if (wi::leu_p (diff, min_seg_len_b) + /* Case A.2 and B combined. */ + || (tree_fits_uhwi_p (dr_a2->seg_len))) + { + if (tree_fits_uhwi_p (dr_a1->seg_len) + && tree_fits_uhwi_p (dr_a2->seg_len)) + new_seg_len + = wide_int_to_tree (sizetype, + wi::umin (wi::sub (dr_a1->seg_len, + diff), + dr_a2->seg_len)); + else + new_seg_len + = size_binop (MINUS_EXPR, dr_a2->seg_len, + wide_int_to_tree (sizetype, diff)); + + dr_a2->seg_len = new_seg_len; + do_remove = true; + } + } 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)) + /* Case A.1. */ + if (wi::leu_p (diff, min_seg_len_b) + /* Case A.2 and B combined. */ + || (tree_fits_uhwi_p (dr_a1->seg_len))) { - dr_a1->seg_len = size_binop (PLUS_EXPR, - dr_a2->seg_len, size_int (diff)); + if (tree_fits_uhwi_p (dr_a1->seg_len) + && tree_fits_uhwi_p (dr_a2->seg_len)) + new_seg_len + = wide_int_to_tree (sizetype, + wi::umax (wi::add (dr_a2->seg_len, + diff), + dr_a1->seg_len)); + else + new_seg_len + = size_binop (PLUS_EXPR, dr_a2->seg_len, + wide_int_to_tree (sizetype, diff)); + + dr_a1->seg_len = new_seg_len; do_remove = true; } } @@ -1334,7 +1386,8 @@ prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs, dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr)); dump_printf (MSG_NOTE, "\n"); } - alias_pairs->ordered_remove (i--); + alias_pairs->ordered_remove (neg_step ? i - 1 : i); + i--; } } }