| Message ID | af6828ae-29f5-7980-5185-dab8c11535a3@gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | constrain one character optimization to one character stores (PR 90989) | expand |
On 6/24/19 5:50 PM, Martin Sebor wrote: > The strlen enhancement committed in r263018 to handle multi-character > assignments extended the handle_char_store() function to handle such > stores via MEM_REFs. Prior to that the function only dealt with > single-char stores. The enhancement neglected to constrain a case > in the function that assumed the function's previous constraint. > As a result, when the original optimization takes place with > a multi-character store, the function computes the wrong string > length. > > The attached patch adds the missing constraint. > > Martin > > gcc-90989.diff > > PR tree-optimization - incorrrect strlen result after second strcpy into > the same destination > > gcc/ChangeLog: > > * tree-ssa-strlen.c (handle_char_store): Constrain a single character > optimization to just single character stores. > > gcc/testsuite/ChangeLog: > > * gcc.dg/strlenopt-26.c: Exit with test result status. > * gcc.dg/strlenopt-67.c: New test. > > Index: gcc/tree-ssa-strlen.c > =================================================================== > --- gcc/tree-ssa-strlen.c (revision 272618) > +++ gcc/tree-ssa-strlen.c (working copy) > @@ -3462,34 +3462,38 @@ handle_char_store (gimple_stmt_iterator *gsi) > return false; > } > } > - /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', > - and if we aren't storing '\0', we know that the length of the > - string and any other zero terminated string in memory remains > - the same. In that case we move to the next gimple statement and > - return to signal the caller that it shouldn't invalidate anything. > > - This is benefical for cases like: > + if (cmp > 0 > + && storing_nonzero_p > + && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) I'm not sure I follow why checking for TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE helps here. If you need to check that we're storing bytes, then don't you need to check the size, not just the TREE_CODE of the type? Jeff
On 6/24/19 5:59 PM, Jeff Law wrote: > On 6/24/19 5:50 PM, Martin Sebor wrote: >> The strlen enhancement committed in r263018 to handle multi-character >> assignments extended the handle_char_store() function to handle such >> stores via MEM_REFs. Prior to that the function only dealt with >> single-char stores. The enhancement neglected to constrain a case >> in the function that assumed the function's previous constraint. >> As a result, when the original optimization takes place with >> a multi-character store, the function computes the wrong string >> length. >> >> The attached patch adds the missing constraint. >> >> Martin >> >> gcc-90989.diff >> >> PR tree-optimization - incorrrect strlen result after second strcpy into >> the same destination >> >> gcc/ChangeLog: >> >> * tree-ssa-strlen.c (handle_char_store): Constrain a single character >> optimization to just single character stores. >> >> gcc/testsuite/ChangeLog: >> >> * gcc.dg/strlenopt-26.c: Exit with test result status. >> * gcc.dg/strlenopt-67.c: New test. >> >> Index: gcc/tree-ssa-strlen.c >> =================================================================== >> --- gcc/tree-ssa-strlen.c (revision 272618) >> +++ gcc/tree-ssa-strlen.c (working copy) >> @@ -3462,34 +3462,38 @@ handle_char_store (gimple_stmt_iterator *gsi) >> return false; >> } >> } >> - /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', >> - and if we aren't storing '\0', we know that the length of the >> - string and any other zero terminated string in memory remains >> - the same. In that case we move to the next gimple statement and >> - return to signal the caller that it shouldn't invalidate anything. >> >> - This is benefical for cases like: >> + if (cmp > 0 >> + && storing_nonzero_p >> + && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) > I'm not sure I follow why checking for TREE_CODE (TREE_TYPE (rhs)) == > INTEGER_TYPE helps here. If you need to check that we're storing bytes, > then don't you need to check the size, not just the TREE_CODE of the type? handle_char_store is only called for single-character assignments or MEM_REF assignments to/from arrays. The type of the RHS is only integer when storing a single character. To determine the number of characters, the subsequent handling in the block below calls get_min_string_length which also relies on INTEGRAL_TYPE_P to get the "length" of a single character (zero or 1). Martin
On 6/24/19 6:47 PM, Martin Sebor wrote: > On 6/24/19 5:59 PM, Jeff Law wrote: >> On 6/24/19 5:50 PM, Martin Sebor wrote: >>> The strlen enhancement committed in r263018 to handle multi-character >>> assignments extended the handle_char_store() function to handle such >>> stores via MEM_REFs. Prior to that the function only dealt with >>> single-char stores. The enhancement neglected to constrain a case >>> in the function that assumed the function's previous constraint. >>> As a result, when the original optimization takes place with >>> a multi-character store, the function computes the wrong string >>> length. >>> >>> The attached patch adds the missing constraint. >>> >>> Martin >>> >>> gcc-90989.diff >>> >>> PR tree-optimization - incorrrect strlen result after second strcpy into >>> the same destination >>> >>> gcc/ChangeLog: >>> >>> * tree-ssa-strlen.c (handle_char_store): Constrain a single >>> character >>> optimization to just single character stores. >>> >>> gcc/testsuite/ChangeLog: >>> >>> * gcc.dg/strlenopt-26.c: Exit with test result status. >>> * gcc.dg/strlenopt-67.c: New test. >>> >>> Index: gcc/tree-ssa-strlen.c >>> =================================================================== >>> --- gcc/tree-ssa-strlen.c (revision 272618) >>> +++ gcc/tree-ssa-strlen.c (working copy) >>> @@ -3462,34 +3462,38 @@ handle_char_store (gimple_stmt_iterator *gsi) >>> return false; >>> } >>> } >>> - /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', >>> - and if we aren't storing '\0', we know that the length of the >>> - string and any other zero terminated string in memory remains >>> - the same. In that case we move to the next gimple statement and >>> - return to signal the caller that it shouldn't invalidate anything. >>> - This is benefical for cases like: >>> + if (cmp > 0 >>> + && storing_nonzero_p >>> + && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) >> I'm not sure I follow why checking for TREE_CODE (TREE_TYPE (rhs)) == >> INTEGER_TYPE helps here. If you need to check that we're storing bytes, >> then don't you need to check the size, not just the TREE_CODE of the >> type? > > handle_char_store is only called for single-character assignments > or MEM_REF assignments to/from arrays. The type of the RHS is only > integer when storing a single character. I don't see any requirement here that INTEGER_TYPE implies a single byte though. That seems to be true in simple tests I've tried, but what's to stop us from using something like 0x31323300 on the RHS for a big endian machine to store "123"? And if the NUL byte in the original was at byte offset 2, then didn't we just change the length by overwriting where the NUL is? ISTM you actually have to look at contents of the RHS object, not just its type. Jeff
On 6/25/19 3:38 PM, Jeff Law wrote: > On 6/24/19 6:47 PM, Martin Sebor wrote: >> On 6/24/19 5:59 PM, Jeff Law wrote: >>> On 6/24/19 5:50 PM, Martin Sebor wrote: >>>> The strlen enhancement committed in r263018 to handle multi-character >>>> assignments extended the handle_char_store() function to handle such >>>> stores via MEM_REFs. Prior to that the function only dealt with >>>> single-char stores. The enhancement neglected to constrain a case >>>> in the function that assumed the function's previous constraint. >>>> As a result, when the original optimization takes place with >>>> a multi-character store, the function computes the wrong string >>>> length. >>>> >>>> The attached patch adds the missing constraint. >>>> >>>> Martin >>>> >>>> gcc-90989.diff >>>> >>>> PR tree-optimization - incorrrect strlen result after second strcpy into >>>> the same destination >>>> >>>> gcc/ChangeLog: >>>> >>>> * tree-ssa-strlen.c (handle_char_store): Constrain a single >>>> character >>>> optimization to just single character stores. >>>> >>>> gcc/testsuite/ChangeLog: >>>> >>>> * gcc.dg/strlenopt-26.c: Exit with test result status. >>>> * gcc.dg/strlenopt-67.c: New test. >>>> >>>> Index: gcc/tree-ssa-strlen.c >>>> =================================================================== >>>> --- gcc/tree-ssa-strlen.c (revision 272618) >>>> +++ gcc/tree-ssa-strlen.c (working copy) >>>> @@ -3462,34 +3462,38 @@ handle_char_store (gimple_stmt_iterator *gsi) >>>> return false; >>>> } >>>> } >>>> - /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', >>>> - and if we aren't storing '\0', we know that the length of the >>>> - string and any other zero terminated string in memory remains >>>> - the same. In that case we move to the next gimple statement and >>>> - return to signal the caller that it shouldn't invalidate anything. >>>> - This is benefical for cases like: >>>> + if (cmp > 0 >>>> + && storing_nonzero_p >>>> + && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) >>> I'm not sure I follow why checking for TREE_CODE (TREE_TYPE (rhs)) == >>> INTEGER_TYPE helps here. If you need to check that we're storing bytes, >>> then don't you need to check the size, not just the TREE_CODE of the >>> type? >> >> handle_char_store is only called for single-character assignments >> or MEM_REF assignments to/from arrays. The type of the RHS is only >> integer when storing a single character. > I don't see any requirement here that INTEGER_TYPE implies a single byte > though. That seems to be true in simple tests I've tried, but what's to > stop us from using something like 0x31323300 on the RHS for a big endian > machine to store "123"? The caller ensures that handle_char_store is only called for stores to arrays (MEM_REF) or single elements as wide as char. What you describe sounds like char a[N]; *(int*)a = 0x31323300; which is represented as MEM[(int *)&b] = 825373440; The LHS type of that is int so the function doesn't get called. > > And if the NUL byte in the original was at byte offset 2, then didn't we > just change the length by overwriting where the NUL is? No, because cmp is the result of compare_nonzero_chars and cmp > 0 means: 1 if SI is known to start with more than OFF nonzero characters i.e., the character is being stored before the terminating nul. This is the basis of the original optimization: /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', and if we aren't storing '\0', we know that the length of the string and any other zero terminated string in memory remains the same. > ISTM you actually have to look at contents of the RHS object, not just > its type. That's already been done earlier by calling initializer_zerop. The function sets storing_nonzero_p when the sequence of characters in RHS is not all zeros. For single integers it calls integer_zerop. Since the type of the RHS is an integer we know the RHS is a single non-zero byte. Martin
On 6/25/19 5:03 PM, Martin Sebor wrote: > > The caller ensures that handle_char_store is only called for stores > to arrays (MEM_REF) or single elements as wide as char. Where? I don't see it, even after fixing the formatting in strlen_check_and_optimize_stmt :-) > gimple *stmt = gsi_stmt (*gsi); > > if (is_gimple_call (stmt)) I think we can agree that we don't have a call, so this is false. > else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt)) > { > tree lhs = gimple_assign_lhs (stmt); This should be true IIUC, so we'll go into its THEN block. > if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs))) Should be false. > else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs))) Should also be false. > else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) Should be true since LHS is a MEM_REF. > { > tree type = TREE_TYPE (lhs); > if (TREE_CODE (type) == ARRAY_TYPE) > type = TREE_TYPE (type); > if (TREE_CODE (type) == INTEGER_TYPE > && TYPE_MODE (type) == TYPE_MODE (char_type_node) > && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node)) > { > if (! handle_char_store (gsi)) > return false; > } > } If TREE_TYPE (type) is an ARRAY_TYPE, we strip the ARRAY_TYPE. We then verify that TYPE is a single character type. _But_ we stripped away the ARRAY_TYPE. So ISTM that we allow either an array of chars or a single char on the LHS. So how does this avoid multiple character stores?!? We could have had an ARRAY_REF on the LHS and we never check the number of elements in the array. There's no check on the RHS either. SO I don't see how we guarantee that we're dealing with a single character store. What am I missing here? > > What you describe sounds like > > char a[N]; > *(int*)a = 0x31323300; > > which is represented as > > MEM[(int *)&b] = 825373440;This would be closer (I realize it's not C): char a[N]; a[0..3] = 0x313233300; > > The LHS type of that is int so the function doesn't get called. I'm concerned about the case where the LHS is an array. >> And if the NUL byte in the original was at byte offset 2, then didn't we >> just change the length by overwriting where the NUL is? > > No, because cmp is the result of compare_nonzero_chars and cmp > 0 > means: > > 1 if SI is known to start with more than OFF nonzero characters > > i.e., the character is being stored before the terminating nul. > This is the basis of the original optimization: > > /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', > and if we aren't storing '\0', we know that the length of the > string and any other zero terminated string in memory remains > the same. But all this is predicated on the assumption that we're dealing with a single character memory store. I don't see what enforces that precondition.
On 6/26/19 4:31 PM, Jeff Law wrote: > On 6/25/19 5:03 PM, Martin Sebor wrote: > >> >> The caller ensures that handle_char_store is only called for stores >> to arrays (MEM_REF) or single elements as wide as char. > Where? I don't see it, even after fixing the formatting in > strlen_check_and_optimize_stmt :-) > >> gimple *stmt = gsi_stmt (*gsi); >> >> if (is_gimple_call (stmt)) > > I think we can agree that we don't have a call, so this is false. > >> else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt)) >> { >> tree lhs = gimple_assign_lhs (stmt); > This should be true IIUC, so we'll go into its THEN block. > > >> if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs))) > Should be false. > >> else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs))) > > Should also be false. > >> else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) > Should be true since LHS is a MEM_REF. > > >> { >> tree type = TREE_TYPE (lhs); >> if (TREE_CODE (type) == ARRAY_TYPE) >> type = TREE_TYPE (type); >> if (TREE_CODE (type) == INTEGER_TYPE >> && TYPE_MODE (type) == TYPE_MODE (char_type_node) >> && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node)) >> { >> if (! handle_char_store (gsi)) >> return false; >> } >> } > If TREE_TYPE (type) is an ARRAY_TYPE, we strip the ARRAY_TYPE. We then > verify that TYPE is a single character type. _But_ we stripped away the > ARRAY_TYPE. So ISTM that we allow either an array of chars or a single > char on the LHS. > > So how does this avoid multiple character stores?!? We could have had > an ARRAY_REF on the LHS and we never check the number of elements in the > array. There's no check on the RHS either. SO I don't see how we > guarantee that we're dealing with a single character store. > > What am I missing here? Can you show me a test case where it breaks? If not, I don't know what you want me to do. I'll just move on to something else. Martin > > > >> >> What you describe sounds like >> >> char a[N]; >> *(int*)a = 0x31323300; >> >> which is represented as >> >> MEM[(int *)&b] = 825373440;This would be closer (I realize it's not C): > > char a[N]; > a[0..3] = 0x313233300; > > >> >> The LHS type of that is int so the function doesn't get called. > I'm concerned about the case where the LHS is an array. > >>> And if the NUL byte in the original was at byte offset 2, then didn't we >>> just change the length by overwriting where the NUL is? >> >> No, because cmp is the result of compare_nonzero_chars and cmp > 0 >> means: >> >> 1 if SI is known to start with more than OFF nonzero characters >> >> i.e., the character is being stored before the terminating nul. >> This is the basis of the original optimization: >> >> /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', >> and if we aren't storing '\0', we know that the length of the >> string and any other zero terminated string in memory remains >> the same. > But all this is predicated on the assumption that we're dealing with a > single character memory store. I don't see what enforces that precondition. >
On 6/26/19 8:40 PM, Martin Sebor wrote: > On 6/26/19 4:31 PM, Jeff Law wrote: >> On 6/25/19 5:03 PM, Martin Sebor wrote: >> >>> >>> The caller ensures that handle_char_store is only called for stores >>> to arrays (MEM_REF) or single elements as wide as char. >> Where? I don't see it, even after fixing the formatting in >> strlen_check_and_optimize_stmt :-) >> >>> gimple *stmt = gsi_stmt (*gsi); >>> >>> if (is_gimple_call (stmt)) >> >> I think we can agree that we don't have a call, so this is false. >> >>> else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt)) >>> { >>> tree lhs = gimple_assign_lhs (stmt); >> This should be true IIUC, so we'll go into its THEN block. >> >> >>> if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE >>> (lhs))) >> Should be false. >> >>> else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P >>> (TREE_TYPE (lhs))) >> >> Should also be false. >> >>> else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) >> Should be true since LHS is a MEM_REF. >> >> >>> { >>> tree type = TREE_TYPE (lhs); >>> if (TREE_CODE (type) == ARRAY_TYPE) >>> type = TREE_TYPE (type); >>> if (TREE_CODE (type) == INTEGER_TYPE >>> && TYPE_MODE (type) == TYPE_MODE (char_type_node) >>> && TYPE_PRECISION (type) == TYPE_PRECISION >>> (char_type_node)) >>> { >>> if (! handle_char_store (gsi)) >>> return false; >>> } >>> } >> If TREE_TYPE (type) is an ARRAY_TYPE, we strip the ARRAY_TYPE. We then >> verify that TYPE is a single character type. _But_ we stripped away the >> ARRAY_TYPE. So ISTM that we allow either an array of chars or a single >> char on the LHS. >> >> So how does this avoid multiple character stores?!? We could have had >> an ARRAY_REF on the LHS and we never check the number of elements in the >> array. There's no check on the RHS either. SO I don't see how we >> guarantee that we're dealing with a single character store. >> >> What am I missing here? > > Can you show me a test case where it breaks? If not, I don't know > what you want me to do. I'll just move on to something else. THe thing to do is research what gimple accepts and what other passes may do. Given this is a code generation bug, "just moving on" isn't really a good option unless we're going to rip out that little bit of code. As I was thinking about this last night, the pass we'd want to look at would be store merging. Let's do that on the call today. jeff
On 6/27/19 9:00 AM, Jeff Law wrote: > On 6/26/19 8:40 PM, Martin Sebor wrote: >> On 6/26/19 4:31 PM, Jeff Law wrote: >>> On 6/25/19 5:03 PM, Martin Sebor wrote: >>> >>>> >>>> The caller ensures that handle_char_store is only called for stores >>>> to arrays (MEM_REF) or single elements as wide as char. >>> Where? I don't see it, even after fixing the formatting in >>> strlen_check_and_optimize_stmt :-) >>> >>>> gimple *stmt = gsi_stmt (*gsi); >>>> >>>> if (is_gimple_call (stmt)) >>> >>> I think we can agree that we don't have a call, so this is false. >>> >>>> else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt)) >>>> { >>>> tree lhs = gimple_assign_lhs (stmt); >>> This should be true IIUC, so we'll go into its THEN block. >>> >>> >>>> if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE >>>> (lhs))) >>> Should be false. >>> >>>> else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P >>>> (TREE_TYPE (lhs))) >>> >>> Should also be false. >>> >>>> else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) >>> Should be true since LHS is a MEM_REF. >>> >>> >>>> { >>>> tree type = TREE_TYPE (lhs); >>>> if (TREE_CODE (type) == ARRAY_TYPE) >>>> type = TREE_TYPE (type); >>>> if (TREE_CODE (type) == INTEGER_TYPE >>>> && TYPE_MODE (type) == TYPE_MODE (char_type_node) >>>> && TYPE_PRECISION (type) == TYPE_PRECISION >>>> (char_type_node)) >>>> { >>>> if (! handle_char_store (gsi)) >>>> return false; >>>> } >>>> } >>> If TREE_TYPE (type) is an ARRAY_TYPE, we strip the ARRAY_TYPE. We then >>> verify that TYPE is a single character type. _But_ we stripped away the >>> ARRAY_TYPE. So ISTM that we allow either an array of chars or a single >>> char on the LHS. >>> >>> So how does this avoid multiple character stores?!? We could have had >>> an ARRAY_REF on the LHS and we never check the number of elements in the >>> array. There's no check on the RHS either. SO I don't see how we >>> guarantee that we're dealing with a single character store. >>> >>> What am I missing here? >> >> Can you show me a test case where it breaks? If not, I don't know >> what you want me to do. I'll just move on to something else. > THe thing to do is research what gimple accepts and what other passes > may do. Given this is a code generation bug, "just moving on" isn't > really a good option unless we're going to rip out that little bit of code. > > As I was thinking about this last night, the pass we'd want to look at > would be store merging. Let's do that on the call today. Actually it was trivial to create with store merging. char x[20]; foo() { x[0] = 0x41; x[1] = 0x42; } MEM <unsigned short> [(char *)&x] = 16961; So clearly we can get this in gimple. So we need a check of some kind, either on the LHS or the RHS to ensure that we actually have a single character store as opposed to something like the above. jeff
On Thu, Jun 27, 2019 at 09:15:41AM -0600, Jeff Law wrote: > Actually it was trivial to create with store merging. > > char x[20]; > foo() > { > x[0] = 0x41; > x[1] = 0x42; > } > > MEM <unsigned short> [(char *)&x] = 16961; > > So clearly we can get this in gimple. So we need a check of some kind, > either on the LHS or the RHS to ensure that we actually have a single > character store as opposed to something like the above. handle_char_store is only called if: tree type = TREE_TYPE (lhs); if (TREE_CODE (type) == ARRAY_TYPE) type = TREE_TYPE (type); if (TREE_CODE (type) == INTEGER_TYPE && TYPE_MODE (type) == TYPE_MODE (char_type_node) && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node)) { if (! handle_char_store (gsi)) return false; } so the above case will not trigger, the only way to call it for multiple character stores is if you have an array. And so far I've succeeded creating that just with strcpy builtin. E.g. the if (storing_all_zeros_p && cmp == 0 && si->full_string_p) { /* When overwriting a '\0' with a '\0', the store can be removed if we know it has been stored in the current function. */ if (!stmt_could_throw_p (cfun, stmt) && si->writable) optimization looks unsafe if we are actually storing more than one zero because then the first zero in there is redundant, but there could be non-zero chars after that and removing the larger all zeros store will keep those other chars with incorrect values; I've tried to reproduce it with: __attribute__((noipa)) void bar (char *x, int l1, int l2) { if (__builtin_memcmp (x, "abcd\0", 6) != 0 || l1 != 4 || l2 != 4) __builtin_abort (); } int main () { char x[64]; __builtin_memset (x, -1, sizeof (x)); asm volatile ("" : : "g" (&x[0]) : "memory"); __builtin_strcpy (x, "abcd"); int l1 = __builtin_strlen (x); #ifdef ONE short __attribute__((may_alias)) *p = (void *) &x[0]; *(p + 2) = 0; #else short *p = (short *) (&x[0] + 4); __builtin_memcpy (p, "\0\0", 2); #endif int l2 = __builtin_strlen (x); bar (x, l1, l2); } but the first case creates a short store, so handle_char_store isn't called, and second for some reason isn't folded from memcpy to a char[2] store. Fundamentally, there is no reason to guard handle_char_store with char or array of char stores, as long as CHAR_BIT == 8 && BITS_PER_UNIT == 8 and native_encode_expr can handle the rhs expression - then we can analyze exactly where is the first '\0' character in there and in the code take it into account. Jakub
On 6/27/19 9:15 AM, Jeff Law wrote: > On 6/27/19 9:00 AM, Jeff Law wrote: >> On 6/26/19 8:40 PM, Martin Sebor wrote: >>> On 6/26/19 4:31 PM, Jeff Law wrote: >>>> On 6/25/19 5:03 PM, Martin Sebor wrote: >>>> >>>>> >>>>> The caller ensures that handle_char_store is only called for stores >>>>> to arrays (MEM_REF) or single elements as wide as char. >>>> Where? I don't see it, even after fixing the formatting in >>>> strlen_check_and_optimize_stmt :-) >>>> >>>>> gimple *stmt = gsi_stmt (*gsi); >>>>> >>>>> if (is_gimple_call (stmt)) >>>> >>>> I think we can agree that we don't have a call, so this is false. >>>> >>>>> else if (is_gimple_assign (stmt) && !gimple_clobber_p (stmt)) >>>>> { >>>>> tree lhs = gimple_assign_lhs (stmt); >>>> This should be true IIUC, so we'll go into its THEN block. >>>> >>>> >>>>> if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE >>>>> (lhs))) >>>> Should be false. >>>> >>>>> else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P >>>>> (TREE_TYPE (lhs))) >>>> >>>> Should also be false. >>>> >>>>> else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) >>>> Should be true since LHS is a MEM_REF. >>>> >>>> >>>>> { >>>>> tree type = TREE_TYPE (lhs); >>>>> if (TREE_CODE (type) == ARRAY_TYPE) >>>>> type = TREE_TYPE (type); >>>>> if (TREE_CODE (type) == INTEGER_TYPE >>>>> && TYPE_MODE (type) == TYPE_MODE (char_type_node) >>>>> && TYPE_PRECISION (type) == TYPE_PRECISION >>>>> (char_type_node)) >>>>> { >>>>> if (! handle_char_store (gsi)) >>>>> return false; >>>>> } >>>>> } >>>> If TREE_TYPE (type) is an ARRAY_TYPE, we strip the ARRAY_TYPE. We then >>>> verify that TYPE is a single character type. _But_ we stripped away the >>>> ARRAY_TYPE. So ISTM that we allow either an array of chars or a single >>>> char on the LHS. >>>> >>>> So how does this avoid multiple character stores?!? We could have had >>>> an ARRAY_REF on the LHS and we never check the number of elements in the >>>> array. There's no check on the RHS either. SO I don't see how we >>>> guarantee that we're dealing with a single character store. >>>> >>>> What am I missing here? >>> >>> Can you show me a test case where it breaks? If not, I don't know >>> what you want me to do. I'll just move on to something else. >> THe thing to do is research what gimple accepts and what other passes >> may do. Given this is a code generation bug, "just moving on" isn't >> really a good option unless we're going to rip out that little bit of code. >> >> As I was thinking about this last night, the pass we'd want to look at >> would be store merging. Let's do that on the call today. > Actually it was trivial to create with store merging. > > char x[20]; > foo() > { > x[0] = 0x41; > x[1] = 0x42; > } > > MEM <unsigned short> [(char *)&x] = 16961; The LHS is unsigned short so handle_char_store would not be called because of the check in the caller. You would need something like: MEM <char[2]> [(char *)&x] = { 'a', 'b' }; or something like that where the type is an array of char. I have no idea if something like it can happen or how. As it is, I'm pretty sure it's not valid (but who knows). > So clearly we can get this in gimple. So we need a check of some kind, > either on the LHS or the RHS to ensure that we actually have a single > character store as opposed to something like the above. As far as I can see that describes the check in the caller. I never said the MEM_REF you show above can't come up in Gimple. What I am saying is that I don't know how to get it to cause a problem here, or even to make it into the function to begin with. Store merging doesn't do it because it runs after strlen. If it did run earlier as I said above, it wouldn't make it into the function. I tried it to convince myself. Without a test case showing how something can happen I don't know what to do to prevent it. You're throwing out hypothetical scenarios based on what's valid Gimple and expect me to write code to handle them. I'm sorry but I don't work that way. I need a test case to see a problem, understand it, and to verify I have fixed it properly. In this instance, I can't think of a problem here, either real or hypothetical, so it's impossible for me to do something to prevent it. Even if the multicharacter store did make it into the function I don't even understand what it is you want me to do -- we'd have to look at the value of the RHS, find a nul in its representation if there is one, and either compute the new string length from it or invalidate the existing length. Either way it's not trivial and would need to be tested to make sure it's correct. So we're back to a test case. Martin PS Here's a test case that can be made to fail but only if a) store merging runs before strlen, and also b) the LHS check above is disabled. char b[4]; int f (const char *s) { __builtin_strcpy (b, "123"); int i = __builtin_strcmp (s, b); b[0] = 'a'; b[1] = 0; // MEM <unsigned short> [(char *)&b] = 97; if (__builtin_strlen (b) != 1) __builtin_abort (); return i; }
On Thu, Jun 27, 2019 at 10:58:25AM -0600, Martin Sebor wrote: > The LHS is unsigned short so handle_char_store would not be called > because of the check in the caller. You would need something like: > > MEM <char[2]> [(char *)&x] = { 'a', 'b' }; This is invalid, because the rhs is non-empty CONSTRUCTOR that doesn't have VECTOR_TYPE - verify_gimple_assign_single has: case CONSTRUCTOR: if (TREE_CODE (rhs1_type) == VECTOR_TYPE) ... else if (CONSTRUCTOR_NELTS (rhs1) != 0) { error ("non-vector %qs with elements", code_name); debug_generic_stmt (rhs1); return true; } But MEM <char[2]> [(char *)&x] = MEM <char[2]> [(char *)"ab"]; is valid. Or = {} would be valid too, even for array stores. Jakub
On June 27, 2019 7:04:32 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote: >On Thu, Jun 27, 2019 at 10:58:25AM -0600, Martin Sebor wrote: >> The LHS is unsigned short so handle_char_store would not be called >> because of the check in the caller. You would need something like: >> >> MEM <char[2]> [(char *)&x] = { 'a', 'b' }; > >This is invalid, because the rhs is non-empty CONSTRUCTOR that doesn't >have >VECTOR_TYPE - verify_gimple_assign_single has: > case CONSTRUCTOR: > if (TREE_CODE (rhs1_type) == VECTOR_TYPE) >... > else if (CONSTRUCTOR_NELTS (rhs1) != 0) > { > error ("non-vector %qs with elements", code_name); > debug_generic_stmt (rhs1); > return true; > } > >But > MEM <char[2]> [(char *)&x] = MEM <char[2]> [(char *)"ab"]; >is valid. Or = {} would be valid too, even for array stores. And you can of course write GIMPLE unit tests for the pass using the GIMPLE FE. Richard. > Jakub
On 6/27/19 11:04 AM, Jakub Jelinek wrote: > On Thu, Jun 27, 2019 at 10:58:25AM -0600, Martin Sebor wrote: >> The LHS is unsigned short so handle_char_store would not be called >> because of the check in the caller. You would need something like: >> >> MEM <char[2]> [(char *)&x] = { 'a', 'b' }; > > This is invalid, because the rhs is non-empty CONSTRUCTOR that doesn't have > VECTOR_TYPE - verify_gimple_assign_single has: > case CONSTRUCTOR: > if (TREE_CODE (rhs1_type) == VECTOR_TYPE) > ... > else if (CONSTRUCTOR_NELTS (rhs1) != 0) > { > error ("non-vector %qs with elements", code_name); > debug_generic_stmt (rhs1); > return true; > } > > But > MEM <char[2]> [(char *)&x] = MEM <char[2]> [(char *)"ab"]; Thanks. A test case that uses this is below. It's handled correctly because the RHS is not all non-zero bytes (storing_nonzero_p is false. The block Jeff is concerned about is the one below: else if (storing_nonzero_p && cmp > 0 && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) { gsi_next (gsi); return false; so what would be needed to show an outstanding problem even with the patch applied (i.e., the INTEGER_TYPE check) is a RHS that's interpreted as all nonzero bytes despite having a nul byte in its representation. I.e., an integer that initializer_zerop() sets the second argument to true for, or tree_expr_nonzero_p (RHS) returns true for. Both initializer_zerop and tree_expr_nonzero_p give up on this representation even though they could handle it because it's a constant. Handling it would be an improvement but it would still return false. What we need is a scalar for the RHS that is non-zero with a nul byte in it. That would do it, but I don't know how to create it or if it's even possible. Martin char b[10]; const char a[2] = "4"; int f (const char *s) { __builtin_strcpy (b, "123"); int i = __builtin_strcmp (s, b); // MEM <unsigned char[2]> [(char * {ref-all})&b] // = MEM <unsigned char[2]> [(char * {ref-all})&a]; __builtin_memcpy (b, a, 2); if (__builtin_strlen (b) != 1) __builtin_abort (); return i; }
On 6/27/19 12:40 PM, Richard Biener wrote: > On June 27, 2019 7:04:32 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote: >> On Thu, Jun 27, 2019 at 10:58:25AM -0600, Martin Sebor wrote: >>> The LHS is unsigned short so handle_char_store would not be called >>> because of the check in the caller. You would need something like: >>> >>> MEM <char[2]> [(char *)&x] = { 'a', 'b' }; >> >> This is invalid, because the rhs is non-empty CONSTRUCTOR that doesn't >> have >> VECTOR_TYPE - verify_gimple_assign_single has: >> case CONSTRUCTOR: >> if (TREE_CODE (rhs1_type) == VECTOR_TYPE) >> ... >> else if (CONSTRUCTOR_NELTS (rhs1) != 0) >> { >> error ("non-vector %qs with elements", code_name); >> debug_generic_stmt (rhs1); >> return true; >> } >> >> But >> MEM <char[2]> [(char *)&x] = MEM <char[2]> [(char *)"ab"]; >> is valid. Or = {} would be valid too, even for array stores. > > And you can of course write GIMPLE unit tests for the pass using the GIMPLE FE. Yea. And this may ultimately be the way we should think about testing this kind of stuff where GIMPLE might allow something that is impossible to express in C or C++. Realistically I don't think any of us can be expected to know the dusty corners of every language. But we ought to be able to reason about what's valid gimple and write tests using the gimple front-end to verify how a particular construct would be handled. jeff
On 6/27/19 10:12 AM, Jakub Jelinek wrote: > On Thu, Jun 27, 2019 at 09:15:41AM -0600, Jeff Law wrote: >> Actually it was trivial to create with store merging. >> >> char x[20]; >> foo() >> { >> x[0] = 0x41; >> x[1] = 0x42; >> } >> >> MEM <unsigned short> [(char *)&x] = 16961; >> >> So clearly we can get this in gimple. So we need a check of some kind, >> either on the LHS or the RHS to ensure that we actually have a single >> character store as opposed to something like the above. > > handle_char_store is only called if: > tree type = TREE_TYPE (lhs); > if (TREE_CODE (type) == ARRAY_TYPE) > type = TREE_TYPE (type); > if (TREE_CODE (type) == INTEGER_TYPE > && TYPE_MODE (type) == TYPE_MODE (char_type_node) > && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node)) > { > if (! handle_char_store (gsi)) > return false; > } > so the above case will not trigger, the only way to call it for multiple > character stores is if you have an array. And so far I've succeeded > creating that just with strcpy builtin. How I could have missed it so many times is a mystery to me. I literally was looking at this on the phone with Martin today for the nth time and my brain just wouldn't parse this code correctly. We can only get into handle_char_store for an LHS that is a character or array of characters. So the only case we have to worry about would be if we have a constant array on the RHS. Something like this from Jakub: MEM <char[2]> [(char *)&x] = MEM <char[2]> [(char *)"ab"]; But in this case the RHS is going to be an ARRAY_TYPE. And thus Martin's new code would reject it because it would only do the optmiization if the RHS has INTEGER_TYPE. So I think my concerns are ultimately a non-issue. FWIW if you're trying to get something like Jakub's assignment, this will do it: char a[7]; int f () { __builtin_strcpy (a, "654321"); } Which results in this being passed to handle_char_store: MEM <unsigned char[7]> [(char * {ref-all})&a] = MEM <unsigned char[7]> [(char * {ref-all})"654321"]; We can make it more problematical by first doing a strcpy into a so that we create an SI structure. Something like this: char a[7]; int f () { strcpy (a, "123"); __builtin_strcpy (a, "654321"); } Compiled with -O2 -fno-tree-dse (the -fno-tree-dse ensures the first strcpy is not eliminated). That should get us into handle_char_store and into the new code from Martin's patch that wants to test: + if (cmp > 0 + && storing_nonzero_p + && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) But the RHS in this case has an ARRAY_TYPE and Martin's test would reject it. So at this point my concerns are alleviated. Jakub, Richi, do either of you have concerns? I've kindof owned the review of this patch from Martin, but since y'all have chimed in, I'd like to give you another chance to chime in before I ACK. jeff ps. FWIW, the gimple FE seems to really dislike constant strings in MEM expressions like we've been working with. It also seems to go into an infinite loop if you've got an extra closing paren on the RHS.. It was still useful to poke at things a bit. One could argue that if we get the FE to a suitable state that it could define what is and what is not valid gimple. That would likely be incredibly help for this kind of stuff.
On Fri, Jun 28, 2019 at 2:16 AM Jeff Law <law@redhat.com> wrote: > > On 6/27/19 10:12 AM, Jakub Jelinek wrote: > > On Thu, Jun 27, 2019 at 09:15:41AM -0600, Jeff Law wrote: > >> Actually it was trivial to create with store merging. > >> > >> char x[20]; > >> foo() > >> { > >> x[0] = 0x41; > >> x[1] = 0x42; > >> } > >> > >> MEM <unsigned short> [(char *)&x] = 16961; > >> > >> So clearly we can get this in gimple. So we need a check of some kind, > >> either on the LHS or the RHS to ensure that we actually have a single > >> character store as opposed to something like the above. > > > > handle_char_store is only called if: > > tree type = TREE_TYPE (lhs); > > if (TREE_CODE (type) == ARRAY_TYPE) > > type = TREE_TYPE (type); > > if (TREE_CODE (type) == INTEGER_TYPE > > && TYPE_MODE (type) == TYPE_MODE (char_type_node) > > && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node)) > > { > > if (! handle_char_store (gsi)) > > return false; > > } > > so the above case will not trigger, the only way to call it for multiple > > character stores is if you have an array. And so far I've succeeded > > creating that just with strcpy builtin. > How I could have missed it so many times is a mystery to me. I > literally was looking at this on the phone with Martin today for the nth > time and my brain just wouldn't parse this code correctly. > > We can only get into handle_char_store for an LHS that is a character or > array of characters. So the only case we have to worry about would be > if we have a constant array on the RHS. Something like this from Jakub: > > MEM <char[2]> [(char *)&x] = MEM <char[2]> [(char *)"ab"]; > > But in this case the RHS is going to be an ARRAY_TYPE. And thus > Martin's new code would reject it because it would only do the > optmiization if the RHS has INTEGER_TYPE. > > So I think my concerns are ultimately a non-issue. > > FWIW if you're trying to get something like Jakub's assignment, this > will do it: > > char a[7]; > int f () > { > __builtin_strcpy (a, "654321"); > } > > Which results in this being passed to handle_char_store: > > MEM <unsigned char[7]> [(char * {ref-all})&a] = MEM <unsigned char[7]> > [(char * {ref-all})"654321"]; > > We can make it more problematical by first doing a strcpy into a so that > we create an SI structure. Something like this: > > char a[7]; > int f () > { > strcpy (a, "123"); > __builtin_strcpy (a, "654321"); > } > > Compiled with -O2 -fno-tree-dse (the -fno-tree-dse ensures the first > strcpy is not eliminated). > > That should get us into handle_char_store and into the new code from > Martin's patch that wants to test: > > > > + if (cmp > 0 > + && storing_nonzero_p > + && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) > > But the RHS in this case has an ARRAY_TYPE and Martin's test would > reject it. > > > So at this point my concerns are alleviated. > > Jakub, Richi, do either of you have concerns? I've kindof owned the > review of this patch from Martin, but since y'all have chimed in, I'd > like to give you another chance to chime in before I ACK. > > jeff > > ps. FWIW, the gimple FE seems to really dislike constant strings in MEM > expressions like we've been working with. It also seems to go into an > infinite loop if you've got an extra closing paren on the RHS.. It was > still useful to poke at things a bit. One could argue that if we get > the FE to a suitable state that it could define what is and what is not > valid gimple. That would likely be incredibly help for this kind of stuff. ;) error handling is a bit weak indeed. I'm testing/committing the following to allow string literals in __MEM which needed string address literals. I guess for Fortran we need to extend this to cover CONST_DECLs which should eventually appear as _Literal (int *) &5 for example. 2019-07-01 Richard Biener <rguenther@suse.de> c/ * gimple-parser.c (c_parser_gimple_postfix_expression): Handle _Literal (char *) &"foo" for address literals pointing to STRING_CSTs. * gcc.dg/gimplefe-42.c: New testcase.
Ping: https://gcc.gnu.org/ml/gcc-patches/2019-06/msg01506.html Jeff (et al.), do you have any outstanding questions/concerns about the patch? Martin On 6/27/19 4:30 PM, Jeff Law wrote: > On 6/27/19 12:40 PM, Richard Biener wrote: >> On June 27, 2019 7:04:32 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote: >>> On Thu, Jun 27, 2019 at 10:58:25AM -0600, Martin Sebor wrote: >>>> The LHS is unsigned short so handle_char_store would not be called >>>> because of the check in the caller. You would need something like: >>>> >>>> MEM <char[2]> [(char *)&x] = { 'a', 'b' }; >>> >>> This is invalid, because the rhs is non-empty CONSTRUCTOR that doesn't >>> have >>> VECTOR_TYPE - verify_gimple_assign_single has: >>> case CONSTRUCTOR: >>> if (TREE_CODE (rhs1_type) == VECTOR_TYPE) >>> ... >>> else if (CONSTRUCTOR_NELTS (rhs1) != 0) >>> { >>> error ("non-vector %qs with elements", code_name); >>> debug_generic_stmt (rhs1); >>> return true; >>> } >>> >>> But >>> MEM <char[2]> [(char *)&x] = MEM <char[2]> [(char *)"ab"]; >>> is valid. Or = {} would be valid too, even for array stores. >> >> And you can of course write GIMPLE unit tests for the pass using the GIMPLE FE. > Yea. And this may ultimately be the way we should think about testing > this kind of stuff where GIMPLE might allow something that is impossible > to express in C or C++. > > Realistically I don't think any of us can be expected to know the dusty > corners of every language. But we ought to be able to reason about > what's valid gimple and write tests using the gimple front-end to verify > how a particular construct would be handled. > > jeff >
On 7/8/19 8:37 PM, Martin Sebor wrote: > Ping: https://gcc.gnu.org/ml/gcc-patches/2019-06/msg01506.html > > Jeff (et al.), do you have any outstanding questions/concerns > about the patch? Sorry I wasn't clear. All my concerns are resolved. The patch is fine for the trunk. jeff >
PR tree-optimization - incorrrect strlen result after second strcpy into the same destination gcc/ChangeLog: * tree-ssa-strlen.c (handle_char_store): Constrain a single character optimization to just single character stores. gcc/testsuite/ChangeLog: * gcc.dg/strlenopt-26.c: Exit with test result status. * gcc.dg/strlenopt-67.c: New test. Index: gcc/testsuite/gcc.dg/strlenopt-26.c =================================================================== --- gcc/testsuite/gcc.dg/strlenopt-26.c (revision 272618) +++ gcc/testsuite/gcc.dg/strlenopt-26.c (working copy) @@ -17,8 +17,7 @@ main (void) { char p[] = "foobar"; const char *volatile q = "xyzzy"; - fn1 (p, q); - return 0; + return fn1 (p, q); } /* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ Index: gcc/testsuite/gcc.dg/strlenopt-67.c =================================================================== --- gcc/testsuite/gcc.dg/strlenopt-67.c (nonexistent) +++ gcc/testsuite/gcc.dg/strlenopt-67.c (working copy) @@ -0,0 +1,52 @@ +/* PR tree-optimization/90989 - incorrrect strlen result after second strcpy + into the same destination. + { dg-do compile } + { dg-options "-O2 -Wall -fdump-tree-optimized" } */ + +// #include "strlenopt.h" + +char a[4]; + +int f4 (void) +{ + char b[4]; + __builtin_strcpy (b, "12"); + + int i = __builtin_strcmp (a, b); + + __builtin_strcpy (b, "123"); + if (__builtin_strlen (b) != 3) + __builtin_abort (); + + return i; +} + +int f6 (void) +{ + char b[6]; + __builtin_strcpy (b, "1234"); + + int i = __builtin_strcmp (a, b); + + __builtin_strcpy (b, "12345"); + if (__builtin_strlen (b) != 5) + __builtin_abort (); + + return i; +} + +int f8 (void) +{ + char b[8]; + __builtin_strcpy (b, "1234"); + + int i = __builtin_strcmp (a, b); + + __builtin_strcpy (b, "1234567"); + if (__builtin_strlen (b) != 7) + __builtin_abort (); + + return i; +} + +/* { dg-final { scan-tree-dump-times "abort|strlen" 0 "optimized" } } */ Index: gcc/tree-ssa-strlen.c =================================================================== --- gcc/tree-ssa-strlen.c (revision 272618) +++ gcc/tree-ssa-strlen.c (working copy) @@ -3462,34 +3462,38 @@ handle_char_store (gimple_stmt_iterator *gsi) return false; } } - /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0', - and if we aren't storing '\0', we know that the length of the - string and any other zero terminated string in memory remains - the same. In that case we move to the next gimple statement and - return to signal the caller that it shouldn't invalidate anything. - This is benefical for cases like: + if (cmp > 0 + && storing_nonzero_p + && TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) + { + /* Handle a single non-nul character store. + If si->nonzero_chars > OFFSET, we aren't overwriting '\0', + and if we aren't storing '\0', we know that the length of the + string and any other zero terminated string in memory remains + the same. In that case we move to the next gimple statement and + return to signal the caller that it shouldn't invalidate anything. - char p[20]; - void foo (char *q) - { - strcpy (p, "foobar"); - size_t len = strlen (p); // This can be optimized into 6 - size_t len2 = strlen (q); // This has to be computed - p[0] = 'X'; - size_t len3 = strlen (p); // This can be optimized into 6 - size_t len4 = strlen (q); // This can be optimized into len2 - bar (len, len2, len3, len4); - } - */ - else if (storing_nonzero_p && cmp > 0) - { + This is benefical for cases like: + + char p[20]; + void foo (char *q) + { + strcpy (p, "foobar"); + size_t len = strlen (p); // can be folded to 6 + size_t len2 = strlen (q); // has to be computed + p[0] = 'X'; + size_t len3 = strlen (p); // can be folded to 6 + size_t len4 = strlen (q); // can be folded to len2 + bar (len, len2, len3, len4); + } */ gsi_next (gsi); return false; } - else if (storing_all_zeros_p - || storing_nonzero_p - || (offset != 0 && cmp > 0)) + + if (storing_all_zeros_p + || storing_nonzero_p + || (offset != 0 && cmp > 0)) { /* When STORING_NONZERO_P, we know that the string will start with at least OFFSET + 1 nonzero characters. If storing