| Message ID | 87mv4iumpq.fsf@linaro.org |
|---|---|
| State | New |
| Headers | show |
| Series | [19/nn] Don't treat zero-sized ranges as overlapping | expand |
On Mon, Oct 23, 2017 at 1:29 PM, Richard Sandiford <richard.sandiford@linaro.org> wrote: > Most GCC ranges seem to be represented as an offset and a size (rather > than a start and inclusive end or start and exclusive end). The usual > test for whether X is in a range is of course: > > x >= start && x < start + size > or: > x >= start && x - start < size > > which means that an empty range of size 0 contains nothing. But other > range tests aren't as obvious. > > The usual test for whether one range is contained within another > range is: > > start1 >= start2 && start1 + size1 <= start2 + size2 > > while the test for whether two ranges overlap (from ranges_overlap_p) is: > > (start1 >= start2 && start1 < start2 + size2) > || (start2 >= start1 && start2 < start1 + size1) > > i.e. the ranges overlap if one range contains the start of the other > range. This leads to strange results like: > > (start X, size 0) is a subrange of (start X, size 0) but > (start X, size 0) does not overlap (start X, size 0) > > Similarly: > > (start 4, size 0) is a subrange of (start 2, size 2) but > (start 4, size 0) does not overlap (start 2, size 2) > > It seems like "X is a subrange of Y" should imply "X overlaps Y". > > This becomes harder to ignore with the runtime sizes and offsets > added for SVE. The most obvious fix seemed to be to say that > an empty range does not overlap anything, and is therefore not > a subrange of anything. > > Using the new definition of subranges didn't seem to cause any > codegen differences in the testsuite. But there was one change > with the new definition of overlapping ranges. strncpy-chk.c has: > > memset (dst, 0, sizeof (dst)); > if (strncpy (dst, src, 0) != dst || strcmp (dst, "")) > abort(); > > The strncpy is detected as a zero-size write, and so with the new > definition of overlapping ranges, we treat the strncpy as having > no effect on the strcmp (which is true). The reaching definition > is the memset instead. > > This patch makes ranges_overlap_p return false for zero-sized > ranges, even if the other range has an unknown size. Ok. Thanks, Richard. > > 2017-10-23 Richard Sandiford <richard.sandiford@linaro.org> > > gcc/ > * tree-ssa-alias.h (ranges_overlap_p): Return false if either > range is known to be empty. > > Index: gcc/tree-ssa-alias.h > =================================================================== > --- gcc/tree-ssa-alias.h 2017-03-28 16:19:22.000000000 +0100 > +++ gcc/tree-ssa-alias.h 2017-10-23 11:47:38.181155696 +0100 > @@ -171,6 +171,8 @@ ranges_overlap_p (HOST_WIDE_INT pos1, > HOST_WIDE_INT pos2, > unsigned HOST_WIDE_INT size2) > { > + if (size1 == 0 || size2 == 0) > + return false; > if (pos1 >= pos2 > && (size2 == (unsigned HOST_WIDE_INT)-1 > || pos1 < (pos2 + (HOST_WIDE_INT) size2)))
Index: gcc/tree-ssa-alias.h =================================================================== --- gcc/tree-ssa-alias.h 2017-03-28 16:19:22.000000000 +0100 +++ gcc/tree-ssa-alias.h 2017-10-23 11:47:38.181155696 +0100 @@ -171,6 +171,8 @@ ranges_overlap_p (HOST_WIDE_INT pos1, HOST_WIDE_INT pos2, unsigned HOST_WIDE_INT size2) { + if (size1 == 0 || size2 == 0) + return false; if (pos1 >= pos2 && (size2 == (unsigned HOST_WIDE_INT)-1 || pos1 < (pos2 + (HOST_WIDE_INT) size2)))
Most GCC ranges seem to be represented as an offset and a size (rather than a start and inclusive end or start and exclusive end). The usual test for whether X is in a range is of course: x >= start && x < start + size or: x >= start && x - start < size which means that an empty range of size 0 contains nothing. But other range tests aren't as obvious. The usual test for whether one range is contained within another range is: start1 >= start2 && start1 + size1 <= start2 + size2 while the test for whether two ranges overlap (from ranges_overlap_p) is: (start1 >= start2 && start1 < start2 + size2) || (start2 >= start1 && start2 < start1 + size1) i.e. the ranges overlap if one range contains the start of the other range. This leads to strange results like: (start X, size 0) is a subrange of (start X, size 0) but (start X, size 0) does not overlap (start X, size 0) Similarly: (start 4, size 0) is a subrange of (start 2, size 2) but (start 4, size 0) does not overlap (start 2, size 2) It seems like "X is a subrange of Y" should imply "X overlaps Y". This becomes harder to ignore with the runtime sizes and offsets added for SVE. The most obvious fix seemed to be to say that an empty range does not overlap anything, and is therefore not a subrange of anything. Using the new definition of subranges didn't seem to cause any codegen differences in the testsuite. But there was one change with the new definition of overlapping ranges. strncpy-chk.c has: memset (dst, 0, sizeof (dst)); if (strncpy (dst, src, 0) != dst || strcmp (dst, "")) abort(); The strncpy is detected as a zero-size write, and so with the new definition of overlapping ranges, we treat the strncpy as having no effect on the strcmp (which is true). The reaching definition is the memset instead. This patch makes ranges_overlap_p return false for zero-sized ranges, even if the other range has an unknown size. 2017-10-23 Richard Sandiford <richard.sandiford@linaro.org> gcc/ * tree-ssa-alias.h (ranges_overlap_p): Return false if either range is known to be empty.