Re: Add a mem_alias_size helper class
On 11/29/2016 03:51 PM, Richard Sandiford wrote: Jeff Lawwrites: On 11/15/2016 09:04 AM, Richard Sandiford wrote: alias.c encodes memory sizes as follows: size > 0: the exact size is known size == 0: the size isn't known size < 0: the exact size of the reference itself is known, but the address has been aligned via AND. In this case "-size" includes the size of the reference and the worst-case number of bytes traversed by the AND. This patch wraps this up in a helper class and associated functions. The new routines fix what seems to be a hole in the old logic: if the size of a reference A was unknown, offset_overlap_p would assume that it could conflict with any other reference B, even if we could prove that B comes before A. The fallback CONSTANT_P (x) && CONSTANT_P (y) case looked incorrect. Either "c" is trustworthy as a distance between the two constants, in which case the alignment handling should work as well there as elsewhere, or "c" isn't trustworthy, in which case offset_overlap_p is unsafe. I think the latter's true; AFAICT we have no evidence that "c" really is the distance between the two references, so using it in the check doesn't make sense. At this point we've excluded cases for which: (a) the base addresses are the same (b) x and y are SYMBOL_REFs, or SYMBOL_REF-based constants wrapped in a CONST (c) x and y are both constant integers No useful cases should be left. As things stood, we would assume that: (mem:SI (const_int X)) could overlap: (mem:SI (symbol_ref Y)) but not: (mem:SI (const (plus (symbol_ref Y) (const_int 4 Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? Thanks, Richard [ This patch is part of the SVE series posted here: https://gcc.gnu.org/ml/gcc/2016-11/msg00030.html ] gcc/ 2016-11-15 Richard Sandiford Alan Hayward David Sherwood * alias.c (mem_alias_size): New class. (mem_alias_size::mode): New function. (mem_alias_size::exact_p): Likewise. (mem_alias_size::max_size_known_p): Likewise. (align_to): Likewise. (alias_may_gt): Likewise. (addr_side_effect_eval): Change type of size argument to mem_alias_size. Use plus_constant. (offset_overlap_p): Change type of xsize and ysize to mem_alias_size. Use alias_may_gt. Don't assume an overlap between an access of unknown size and an access that's known to be earlier than it. (memrefs_conflict_p): Change type of xsize and ysize to mem_alias_size. Remove fallback CONSTANT_P (x) && CONSTANT_P (y) handling. OK. One possible nit below you might want to consider changing. +/* Represents the size of a memory reference during alias analysis. + There are three possibilities: -/* Set up all info needed to perform alias analysis on memory references. */ + (1) the size needs to be treated as completely unknown + (2) the size is known exactly and no alignment is applied to the address + (3) the size is known exactly but an alignment is applied to the address + + (3) is used for aligned addresses of the form (and X (const_int -N)), + which can subtract something in the range [0, N) from the original + address X. We handle this by subtracting N - 1 from X and adding N - 1 + to the size, so that the range spans all possible bytes. */ +class mem_alias_size { +public: + /* Return an unknown size (case (1) above). */ + static mem_alias_size unknown () { return (HOST_WIDE_INT) 0; } + + /* Return an exact size (case (2) above). */ + static mem_alias_size exact (HOST_WIDE_INT size) { return size; } + + /* Return a worst-case size after alignment (case (3) above). + SIZE includes the maximum adjustment applied by the alignment. */ + static mem_alias_size aligned (HOST_WIDE_INT size) { return -size; } + + /* Return the size of memory reference X. */ + static mem_alias_size mem (const_rtx x) { return MEM_SIZE (x); } + + static mem_alias_size mode (machine_mode m); + + /* Return true if the exact size of the memory is known. */ + bool exact_p () const { return m_value > 0; } + bool exact_p (HOST_WIDE_INT *) const; + + /* Return true if an upper bound on the memory size is known; + i.e. not case (1) above. */ + bool max_size_known_p () const { return m_value != 0; } + bool max_size_known_p (HOST_WIDE_INT *) const; + + /* Return true if the size is subject to alignment. */ + bool aligned_p () const { return m_value < 0; } + +private: + mem_alias_size (HOST_WIDE_INT value) : m_value (value) {} + + HOST_WIDE_INT m_value; +}; If I were to see a call to the aligned_p method, my first thought is testing if an object is properly aligned. This method actually tells us something different -- was the size adjusted to account for alignment issues. In fact, when I was reading the memrefs_conflict_p
Re: Add a mem_alias_size helper class
Jeff Lawwrites: > On 11/15/2016 09:04 AM, Richard Sandiford wrote: >> alias.c encodes memory sizes as follows: >> >> size > 0: the exact size is known >> size == 0: the size isn't known >> size < 0: the exact size of the reference itself is known, >> but the address has been aligned via AND. In this case >> "-size" includes the size of the reference and the worst-case >> number of bytes traversed by the AND. >> >> This patch wraps this up in a helper class and associated >> functions. The new routines fix what seems to be a hole >> in the old logic: if the size of a reference A was unknown, >> offset_overlap_p would assume that it could conflict with any >> other reference B, even if we could prove that B comes before A. >> >> The fallback CONSTANT_P (x) && CONSTANT_P (y) case looked incorrect. >> Either "c" is trustworthy as a distance between the two constants, >> in which case the alignment handling should work as well there as >> elsewhere, or "c" isn't trustworthy, in which case offset_overlap_p >> is unsafe. I think the latter's true; AFAICT we have no evidence >> that "c" really is the distance between the two references, so using >> it in the check doesn't make sense. >> >> At this point we've excluded cases for which: >> >> (a) the base addresses are the same >> (b) x and y are SYMBOL_REFs, or SYMBOL_REF-based constants >> wrapped in a CONST >> (c) x and y are both constant integers >> >> No useful cases should be left. As things stood, we would >> assume that: >> >> (mem:SI (const_int X)) >> >> could overlap: >> >> (mem:SI (symbol_ref Y)) >> >> but not: >> >> (mem:SI (const (plus (symbol_ref Y) (const_int 4 >> >> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? >> >> Thanks, >> Richard >> >> >> [ This patch is part of the SVE series posted here: >> https://gcc.gnu.org/ml/gcc/2016-11/msg00030.html ] >> >> gcc/ >> 2016-11-15 Richard Sandiford >> Alan Hayward >> David Sherwood >> >> * alias.c (mem_alias_size): New class. >> (mem_alias_size::mode): New function. >> (mem_alias_size::exact_p): Likewise. >> (mem_alias_size::max_size_known_p): Likewise. >> (align_to): Likewise. >> (alias_may_gt): Likewise. >> (addr_side_effect_eval): Change type of size argument to >> mem_alias_size. Use plus_constant. >> (offset_overlap_p): Change type of xsize and ysize to >> mem_alias_size. Use alias_may_gt. Don't assume an overlap >> between an access of unknown size and an access that's known >> to be earlier than it. >> (memrefs_conflict_p): Change type of xsize and ysize to >> mem_alias_size. Remove fallback CONSTANT_P (x) && CONSTANT_P (y) >> handling. > OK. One possible nit below you might want to consider changing. > >> +/* Represents the size of a memory reference during alias analysis. >> + There are three possibilities: >> >> -/* Set up all info needed to perform alias analysis on memory references. >> */ >> + (1) the size needs to be treated as completely unknown >> + (2) the size is known exactly and no alignment is applied to the address >> + (3) the size is known exactly but an alignment is applied to the address >> + >> + (3) is used for aligned addresses of the form (and X (const_int -N)), >> + which can subtract something in the range [0, N) from the original >> + address X. We handle this by subtracting N - 1 from X and adding N - 1 >> + to the size, so that the range spans all possible bytes. */ >> +class mem_alias_size { >> +public: >> + /* Return an unknown size (case (1) above). */ >> + static mem_alias_size unknown () { return (HOST_WIDE_INT) 0; } >> + >> + /* Return an exact size (case (2) above). */ >> + static mem_alias_size exact (HOST_WIDE_INT size) { return size; } >> + >> + /* Return a worst-case size after alignment (case (3) above). >> + SIZE includes the maximum adjustment applied by the alignment. */ >> + static mem_alias_size aligned (HOST_WIDE_INT size) { return -size; } >> + >> + /* Return the size of memory reference X. */ >> + static mem_alias_size mem (const_rtx x) { return MEM_SIZE (x); } >> + >> + static mem_alias_size mode (machine_mode m); >> + >> + /* Return true if the exact size of the memory is known. */ >> + bool exact_p () const { return m_value > 0; } >> + bool exact_p (HOST_WIDE_INT *) const; >> + >> + /* Return true if an upper bound on the memory size is known; >> + i.e. not case (1) above. */ >> + bool max_size_known_p () const { return m_value != 0; } >> + bool max_size_known_p (HOST_WIDE_INT *) const; >> + >> + /* Return true if the size is subject to alignment. */ >> + bool aligned_p () const { return m_value < 0; } >> + >> +private: >> + mem_alias_size (HOST_WIDE_INT value) : m_value (value) {} >> + >> + HOST_WIDE_INT m_value; >> +}; > If I were to see a call to the
Re: Add a mem_alias_size helper class
On 11/15/2016 09:04 AM, Richard Sandiford wrote: alias.c encodes memory sizes as follows: size > 0: the exact size is known size == 0: the size isn't known size < 0: the exact size of the reference itself is known, but the address has been aligned via AND. In this case "-size" includes the size of the reference and the worst-case number of bytes traversed by the AND. This patch wraps this up in a helper class and associated functions. The new routines fix what seems to be a hole in the old logic: if the size of a reference A was unknown, offset_overlap_p would assume that it could conflict with any other reference B, even if we could prove that B comes before A. The fallback CONSTANT_P (x) && CONSTANT_P (y) case looked incorrect. Either "c" is trustworthy as a distance between the two constants, in which case the alignment handling should work as well there as elsewhere, or "c" isn't trustworthy, in which case offset_overlap_p is unsafe. I think the latter's true; AFAICT we have no evidence that "c" really is the distance between the two references, so using it in the check doesn't make sense. At this point we've excluded cases for which: (a) the base addresses are the same (b) x and y are SYMBOL_REFs, or SYMBOL_REF-based constants wrapped in a CONST (c) x and y are both constant integers No useful cases should be left. As things stood, we would assume that: (mem:SI (const_int X)) could overlap: (mem:SI (symbol_ref Y)) but not: (mem:SI (const (plus (symbol_ref Y) (const_int 4 Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? Thanks, Richard [ This patch is part of the SVE series posted here: https://gcc.gnu.org/ml/gcc/2016-11/msg00030.html ] gcc/ 2016-11-15 Richard SandifordAlan Hayward David Sherwood * alias.c (mem_alias_size): New class. (mem_alias_size::mode): New function. (mem_alias_size::exact_p): Likewise. (mem_alias_size::max_size_known_p): Likewise. (align_to): Likewise. (alias_may_gt): Likewise. (addr_side_effect_eval): Change type of size argument to mem_alias_size. Use plus_constant. (offset_overlap_p): Change type of xsize and ysize to mem_alias_size. Use alias_may_gt. Don't assume an overlap between an access of unknown size and an access that's known to be earlier than it. (memrefs_conflict_p): Change type of xsize and ysize to mem_alias_size. Remove fallback CONSTANT_P (x) && CONSTANT_P (y) handling. OK. One possible nit below you might want to consider changing. +/* Represents the size of a memory reference during alias analysis. + There are three possibilities: -/* Set up all info needed to perform alias analysis on memory references. */ + (1) the size needs to be treated as completely unknown + (2) the size is known exactly and no alignment is applied to the address + (3) the size is known exactly but an alignment is applied to the address + + (3) is used for aligned addresses of the form (and X (const_int -N)), + which can subtract something in the range [0, N) from the original + address X. We handle this by subtracting N - 1 from X and adding N - 1 + to the size, so that the range spans all possible bytes. */ +class mem_alias_size { +public: + /* Return an unknown size (case (1) above). */ + static mem_alias_size unknown () { return (HOST_WIDE_INT) 0; } + + /* Return an exact size (case (2) above). */ + static mem_alias_size exact (HOST_WIDE_INT size) { return size; } + + /* Return a worst-case size after alignment (case (3) above). + SIZE includes the maximum adjustment applied by the alignment. */ + static mem_alias_size aligned (HOST_WIDE_INT size) { return -size; } + + /* Return the size of memory reference X. */ + static mem_alias_size mem (const_rtx x) { return MEM_SIZE (x); } + + static mem_alias_size mode (machine_mode m); + + /* Return true if the exact size of the memory is known. */ + bool exact_p () const { return m_value > 0; } + bool exact_p (HOST_WIDE_INT *) const; + + /* Return true if an upper bound on the memory size is known; + i.e. not case (1) above. */ + bool max_size_known_p () const { return m_value != 0; } + bool max_size_known_p (HOST_WIDE_INT *) const; + + /* Return true if the size is subject to alignment. */ + bool aligned_p () const { return m_value < 0; } + +private: + mem_alias_size (HOST_WIDE_INT value) : m_value (value) {} + + HOST_WIDE_INT m_value; +}; If I were to see a call to the aligned_p method, my first thought is testing if an object is properly aligned. This method actually tells us something different -- was the size adjusted to account for alignment issues. In fact, when I was reading the memrefs_conflict_p changes that's the mistake I nearly called the code out as wrong. Then I went back
Re: Add a mem_alias_size helper class
Eric Botcazouwrites: >> alias.c encodes memory sizes as follows: >> >> size > 0: the exact size is known >> size == 0: the size isn't known >> size < 0: the exact size of the reference itself is known, >> but the address has been aligned via AND. In this case >> "-size" includes the size of the reference and the worst-case >> number of bytes traversed by the AND. >> >> This patch wraps this up in a helper class and associated >> functions. The new routines fix what seems to be a hole >> in the old logic: if the size of a reference A was unknown, >> offset_overlap_p would assume that it could conflict with any >> other reference B, even if we could prove that B comes before A. >> >> The fallback CONSTANT_P (x) && CONSTANT_P (y) case looked incorrect. >> Either "c" is trustworthy as a distance between the two constants, >> in which case the alignment handling should work as well there as >> elsewhere, or "c" isn't trustworthy, in which case offset_overlap_p >> is unsafe. I think the latter's true; AFAICT we have no evidence >> that "c" really is the distance between the two references, so using >> it in the check doesn't make sense. >> >> At this point we've excluded cases for which: >> >> (a) the base addresses are the same >> (b) x and y are SYMBOL_REFs, or SYMBOL_REF-based constants >> wrapped in a CONST >> (c) x and y are both constant integers >> >> No useful cases should be left. As things stood, we would >> assume that: >> >> (mem:SI (const_int X)) >> >> could overlap: >> >> (mem:SI (symbol_ref Y)) >> >> but not: >> >> (mem:SI (const (plus (symbol_ref Y) (const_int 4 > > Frankly this seems to be an example of counter-productive C++ization: the > class doesn't provide any useful abstraction and the code gets obfuscated by > all the wrapper methods. Moreover it's mixed with real changes so very hard > to review. Can't you just fix what needs to be fixed first? Sorry, I should have said, but this wasn't C++-ification for its own sake. It was part of the changes to make modes and MEM_OFFSETs be runtime invariants of the form a+bX for runtime X. Making that change to modes and MEM_OFFSETs meant that these alias sizes also become runtime invariants. The classification above is then: size may be greater than 0: the exact size is known size must be equal to 0: the size is unknown size may be less than 0: -size is the maximum size including alignment with the assumption that a and b cannot be such that a+bX>0 for some X and <0 for other X. So we were faced the prospect of having to change every existing ==0, >0 and <0 test anyway. The question was whether to change them to "may be greater than 0?" etc. or change them to something more mnemonic like "exact size known?". The latter seemed better. That part in itself could be done using inline functions. What the class gives is that it also enforces statically that the restrictions on a and b above hold, i.e. that a+bX is always ordered wrt 0. Similarly, abs(a+bX) cannot be represented as a'+b'X for all a and b, so abs() is not unconditionally computable on these runtime invariants. The use of abs() on the encoded sizes would therefore also need either a wrapper like "max_size" or a cut-&-paste change to cope with the fact that abs() is always computable on these sizes. Using the more mnemonic "max_size" seemed better than preserving the use of "abs"; to me, abs implies we have a negative displacement from an end point, whereas really the sign bit is being used as a boolean to indicate inexactness. Again, "max_size" could just be an inline function, but the class enforces statically that abs() is computable. We separated the patch out because it made the actual switch to support runtime invariants almost mechanical. Thanks, Richard
Re: Add a mem_alias_size helper class
> alias.c encodes memory sizes as follows: > > size > 0: the exact size is known > size == 0: the size isn't known > size < 0: the exact size of the reference itself is known, > but the address has been aligned via AND. In this case > "-size" includes the size of the reference and the worst-case > number of bytes traversed by the AND. > > This patch wraps this up in a helper class and associated > functions. The new routines fix what seems to be a hole > in the old logic: if the size of a reference A was unknown, > offset_overlap_p would assume that it could conflict with any > other reference B, even if we could prove that B comes before A. > > The fallback CONSTANT_P (x) && CONSTANT_P (y) case looked incorrect. > Either "c" is trustworthy as a distance between the two constants, > in which case the alignment handling should work as well there as > elsewhere, or "c" isn't trustworthy, in which case offset_overlap_p > is unsafe. I think the latter's true; AFAICT we have no evidence > that "c" really is the distance between the two references, so using > it in the check doesn't make sense. > > At this point we've excluded cases for which: > > (a) the base addresses are the same > (b) x and y are SYMBOL_REFs, or SYMBOL_REF-based constants > wrapped in a CONST > (c) x and y are both constant integers > > No useful cases should be left. As things stood, we would > assume that: > > (mem:SI (const_int X)) > > could overlap: > > (mem:SI (symbol_ref Y)) > > but not: > > (mem:SI (const (plus (symbol_ref Y) (const_int 4 Frankly this seems to be an example of counter-productive C++ization: the class doesn't provide any useful abstraction and the code gets obfuscated by all the wrapper methods. Moreover it's mixed with real changes so very hard to review. Can't you just fix what needs to be fixed first? -- Eric Botcazou
Add a mem_alias_size helper class
alias.c encodes memory sizes as follows: size > 0: the exact size is known size == 0: the size isn't known size < 0: the exact size of the reference itself is known, but the address has been aligned via AND. In this case "-size" includes the size of the reference and the worst-case number of bytes traversed by the AND. This patch wraps this up in a helper class and associated functions. The new routines fix what seems to be a hole in the old logic: if the size of a reference A was unknown, offset_overlap_p would assume that it could conflict with any other reference B, even if we could prove that B comes before A. The fallback CONSTANT_P (x) && CONSTANT_P (y) case looked incorrect. Either "c" is trustworthy as a distance between the two constants, in which case the alignment handling should work as well there as elsewhere, or "c" isn't trustworthy, in which case offset_overlap_p is unsafe. I think the latter's true; AFAICT we have no evidence that "c" really is the distance between the two references, so using it in the check doesn't make sense. At this point we've excluded cases for which: (a) the base addresses are the same (b) x and y are SYMBOL_REFs, or SYMBOL_REF-based constants wrapped in a CONST (c) x and y are both constant integers No useful cases should be left. As things stood, we would assume that: (mem:SI (const_int X)) could overlap: (mem:SI (symbol_ref Y)) but not: (mem:SI (const (plus (symbol_ref Y) (const_int 4 Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? Thanks, Richard [ This patch is part of the SVE series posted here: https://gcc.gnu.org/ml/gcc/2016-11/msg00030.html ] gcc/ 2016-11-15 Richard SandifordAlan Hayward David Sherwood * alias.c (mem_alias_size): New class. (mem_alias_size::mode): New function. (mem_alias_size::exact_p): Likewise. (mem_alias_size::max_size_known_p): Likewise. (align_to): Likewise. (alias_may_gt): Likewise. (addr_side_effect_eval): Change type of size argument to mem_alias_size. Use plus_constant. (offset_overlap_p): Change type of xsize and ysize to mem_alias_size. Use alias_may_gt. Don't assume an overlap between an access of unknown size and an access that's known to be earlier than it. (memrefs_conflict_p): Change type of xsize and ysize to mem_alias_size. Remove fallback CONSTANT_P (x) && CONSTANT_P (y) handling. diff --git a/gcc/alias.c b/gcc/alias.c index 1ea2417..486d06a 100644 --- a/gcc/alias.c +++ b/gcc/alias.c @@ -148,7 +148,6 @@ struct GTY(()) alias_set_entry { }; static int rtx_equal_for_memref_p (const_rtx, const_rtx); -static int memrefs_conflict_p (int, rtx, int, rtx, HOST_WIDE_INT); static void record_set (rtx, const_rtx, void *); static int base_alias_check (rtx, rtx, rtx, rtx, machine_mode, machine_mode); @@ -176,11 +175,104 @@ static struct { unsigned long long num_disambiguated; } alias_stats; +/* Represents the size of a memory reference during alias analysis. + There are three possibilities: -/* Set up all info needed to perform alias analysis on memory references. */ + (1) the size needs to be treated as completely unknown + (2) the size is known exactly and no alignment is applied to the address + (3) the size is known exactly but an alignment is applied to the address + + (3) is used for aligned addresses of the form (and X (const_int -N)), + which can subtract something in the range [0, N) from the original + address X. We handle this by subtracting N - 1 from X and adding N - 1 + to the size, so that the range spans all possible bytes. */ +class mem_alias_size { +public: + /* Return an unknown size (case (1) above). */ + static mem_alias_size unknown () { return (HOST_WIDE_INT) 0; } + + /* Return an exact size (case (2) above). */ + static mem_alias_size exact (HOST_WIDE_INT size) { return size; } + + /* Return a worst-case size after alignment (case (3) above). + SIZE includes the maximum adjustment applied by the alignment. */ + static mem_alias_size aligned (HOST_WIDE_INT size) { return -size; } + + /* Return the size of memory reference X. */ + static mem_alias_size mem (const_rtx x) { return MEM_SIZE (x); } + + static mem_alias_size mode (machine_mode m); + + /* Return true if the exact size of the memory is known. */ + bool exact_p () const { return m_value > 0; } + bool exact_p (HOST_WIDE_INT *) const; + + /* Return true if an upper bound on the memory size is known; + i.e. not case (1) above. */ + bool max_size_known_p () const { return m_value != 0; } + bool max_size_known_p (HOST_WIDE_INT *) const; + + /* Return true if the size is subject to alignment. */ + bool aligned_p () const { return m_value < 0; } + +private: + mem_alias_size