| Message ID | 87efw3sebf.fsf@linaro.org |
|---|---|
| State | New |
| Headers | show |
Richard Sandiford <richard.sandiford@linaro.org> writes: > tree-ssa-strlen.c looks for cases in which a string is built up using > operations like: > > memcpy (a, "foo", 4); > memcpy (a + 3, "bar", 4); > int x = strlen (a); > > As a side-effect, it optimises the non-final memcpys so that they don't > include the nul terminator. > > However, after removing some "& ~0x1"s from tree-ssa-dse.c, the DSE pass > does this optimisation itself (because it can tell that later memcpys > overwrite the terminators). The strlen pass wasn't able to handle these > pre-optimised calls in the same way as the unoptimised ones. > > This patch adds support for tracking unterminated strings. Would that be useful as a warning too? If the pass can figure out the final string can be not null terminated when passed somewhere else, warn, because it's likely a bug in the program. -Andi
On Fri, May 05, 2017 at 08:50:04AM -0700, Andi Kleen wrote: > Richard Sandiford <richard.sandiford@linaro.org> writes: > > > tree-ssa-strlen.c looks for cases in which a string is built up using > > operations like: > > > > memcpy (a, "foo", 4); > > memcpy (a + 3, "bar", 4); > > int x = strlen (a); > > > > As a side-effect, it optimises the non-final memcpys so that they don't > > include the nul terminator. > > > > However, after removing some "& ~0x1"s from tree-ssa-dse.c, the DSE pass > > does this optimisation itself (because it can tell that later memcpys > > overwrite the terminators). The strlen pass wasn't able to handle these > > pre-optimised calls in the same way as the unoptimised ones. > > > > This patch adds support for tracking unterminated strings. > > Would that be useful as a warning too? If the pass can figure out > the final string can be not null terminated when passed somewhere else, > warn, because it's likely a bug in the program. Why would it be a bug? Not all sequences of chars are zero terminated strings, it can be arbitrary memory and have size somewhere on the side. Also, the fact that strlen pass sees a memcpy (a, "foo", 3); and a passed somewhere else doesn't mean a isn't zero terminated, the pass records only what it can prove, so even when you have: memcpy (a, "abcdefgh", 9); *p = 0; // unrelated pointer, but compiler can't prove that memcpy (a, "foo", 3); call (a); there is really nothing wrong with it, the string is still zero terminated. The pass had to flush the knowledge that it knew length of a on the wild pointer store. Jakub
On Fri, May 05, 2017 at 01:01:08PM +0100, Richard Sandiford wrote: > tree-ssa-strlen.c looks for cases in which a string is built up using > operations like: > > memcpy (a, "foo", 4); > memcpy (a + 3, "bar", 4); > int x = strlen (a); > > As a side-effect, it optimises the non-final memcpys so that they don't > include the nul terminator. > > However, after removing some "& ~0x1"s from tree-ssa-dse.c, the DSE pass > does this optimisation itself (because it can tell that later memcpys > overwrite the terminators). The strlen pass wasn't able to handle these > pre-optimised calls in the same way as the unoptimised ones. > > This patch adds support for tracking unterminated strings. I'm not sure I like the terminology (terminated vs. !terminated), I wonder if it wouldn't be better to add next to length field minimum_length field, length would be what it is now, tree representing the string length, while minimum_length would be just a guarantee that strlen (ptr) >= minimum_length, i.e. that in the first minimum_length bytes (best would be to guarantee that it is just a constant if non-NULL) are non-zero. It shouldn't be handled just by non-zero terminated memcpy, but e.g. even if you e.g. construct it byte by byte, etc. a[0] = 'a'; a[1] = 'b'; a[2] = 'c'; a[3] = 'd'; a[4] = '\0'; x = strlen (a); etc., or strcpy (a, "abcdefg"); strcpy (a + 8, "hijk"); a[7] = 'q'; x = strlen (a); or say by storing 4 non-zero bytes at a time... Jakub
On 05/05/2017 06:01 AM, Richard Sandiford wrote: > tree-ssa-strlen.c looks for cases in which a string is built up using > operations like: > > memcpy (a, "foo", 4); > memcpy (a + 3, "bar", 4); > int x = strlen (a); > > As a side-effect, it optimises the non-final memcpys so that they don't > include the nul terminator. > > However, after removing some "& ~0x1"s from tree-ssa-dse.c, the DSE pass > does this optimisation itself (because it can tell that later memcpys > overwrite the terminators). The strlen pass wasn't able to handle these > pre-optimised calls in the same way as the unoptimised ones. > > This patch adds support for tracking unterminated strings. Oooh, very nice! :) I spent some time on something like this last summer (under bug 71304) but didn't finish it. My patch also handled NULs inserted by simple assignment. I see your patch handles them when they are inserted by a call to one of the functions but not otherwise, as in the test case below. Is that something that could be easily handled in your approach? char a[30]; int f1 (void) { __builtin_memcpy (a, "1234567", 7); __builtin_memcpy (a + 7, "", 1); return __builtin_strlen (a); // is optimized to 7 } int f2 (void) { __builtin_memcpy (a, "1234567", 7); a[7] = '\0'; return __builtin_strlen (a); // could be optimized to 7 } Martin
On 05/05/2017 09:55 AM, Jakub Jelinek wrote: > On Fri, May 05, 2017 at 08:50:04AM -0700, Andi Kleen wrote: >> Richard Sandiford <richard.sandiford@linaro.org> writes: >> >>> tree-ssa-strlen.c looks for cases in which a string is built up using >>> operations like: >>> >>> memcpy (a, "foo", 4); >>> memcpy (a + 3, "bar", 4); >>> int x = strlen (a); >>> >>> As a side-effect, it optimises the non-final memcpys so that they don't >>> include the nul terminator. >>> >>> However, after removing some "& ~0x1"s from tree-ssa-dse.c, the DSE pass >>> does this optimisation itself (because it can tell that later memcpys >>> overwrite the terminators). The strlen pass wasn't able to handle these >>> pre-optimised calls in the same way as the unoptimised ones. >>> >>> This patch adds support for tracking unterminated strings. >> >> Would that be useful as a warning too? If the pass can figure out >> the final string can be not null terminated when passed somewhere else, >> warn, because it's likely a bug in the program. > > Why would it be a bug? Not all sequences of chars are zero terminated > strings, it can be arbitrary memory and have size somewhere on the side. > Also, the fact that strlen pass sees a memcpy (a, "foo", 3); and a passed > somewhere else doesn't mean a isn't zero terminated, the pass records only > what it can prove, so even when you have: > memcpy (a, "abcdefgh", 9); > *p = 0; // unrelated pointer, but compiler can't prove that > memcpy (a, "foo", 3); > call (a); There have been requests for a warning to diagnose invalid uses of character arrays that are not nul-terminated, such as arguments to functions that expect a (nul-terminated) string. For example: char *p = (char*)malloc (20); memcpy (p, "/tmp/", 5); strcat (p, "file.text"); // << warn here It would be helpful to diagnose such cases (while avoiding false positives on the indeterminate cases you mention, of course). Martin
On Fri, May 05, 2017 at 10:28:45AM -0600, Martin Sebor wrote: > There have been requests for a warning to diagnose invalid uses > of character arrays that are not nul-terminated, such as arguments > to functions that expect a (nul-terminated) string. For example: > > char *p = (char*)malloc (20); > memcpy (p, "/tmp/", 5); > strcat (p, "file.text"); // << warn here > > It would be helpful to diagnose such cases (while avoiding false > positives on the indeterminate cases you mention, of course). One thing here is that there is a function known to require a null terminated function, not arbitrary other function that may or might not need it. And another thing is that in the tree-ssa-strlen.c framework known records can be invalidated at any time and you then don't know, it is an optimization, not a warning framework. So, for the warning you'd need to track whether there have been any invalidation and just punt in that case. Jakub
On 05/05/2017 10:28 AM, Martin Sebor wrote: > On 05/05/2017 09:55 AM, Jakub Jelinek wrote: >> On Fri, May 05, 2017 at 08:50:04AM -0700, Andi Kleen wrote: >>> Richard Sandiford <richard.sandiford@linaro.org> writes: >>> >>>> tree-ssa-strlen.c looks for cases in which a string is built up using >>>> operations like: >>>> >>>> memcpy (a, "foo", 4); >>>> memcpy (a + 3, "bar", 4); >>>> int x = strlen (a); >>>> >>>> As a side-effect, it optimises the non-final memcpys so that they don't >>>> include the nul terminator. >>>> >>>> However, after removing some "& ~0x1"s from tree-ssa-dse.c, the DSE >>>> pass >>>> does this optimisation itself (because it can tell that later memcpys >>>> overwrite the terminators). The strlen pass wasn't able to handle >>>> these >>>> pre-optimised calls in the same way as the unoptimised ones. >>>> >>>> This patch adds support for tracking unterminated strings. >>> >>> Would that be useful as a warning too? If the pass can figure out >>> the final string can be not null terminated when passed somewhere else, >>> warn, because it's likely a bug in the program. >> >> Why would it be a bug? Not all sequences of chars are zero terminated >> strings, it can be arbitrary memory and have size somewhere on the side. >> Also, the fact that strlen pass sees a memcpy (a, "foo", 3); and a passed >> somewhere else doesn't mean a isn't zero terminated, the pass records >> only >> what it can prove, so even when you have: >> memcpy (a, "abcdefgh", 9); >> *p = 0; // unrelated pointer, but compiler can't prove that >> memcpy (a, "foo", 3); >> call (a); > > There have been requests for a warning to diagnose invalid uses > of character arrays that are not nul-terminated, such as arguments > to functions that expect a (nul-terminated) string. For example: > > char *p = (char*)malloc (20); > memcpy (p, "/tmp/", 5); > strcat (p, "file.text"); // << warn here > > It would be helpful to diagnose such cases (while avoiding false > positives on the indeterminate cases you mention, of course). Can't we just start at point where the string must be terminated (strcat call in this case) and walk the VUSE/VDEF chain back to determine if object's NUL termination status is: 1. Terminated 2. Not terminated 3. Indeterminate You'd probably want to have some kind of propagation step so that you don't just give up when you see a PHI node. Instead you recurse on the PHI args before determining the state at the PHI itself. Jeff
On 05/05/2017 10:32 AM, Jakub Jelinek wrote: > On Fri, May 05, 2017 at 10:28:45AM -0600, Martin Sebor wrote: >> There have been requests for a warning to diagnose invalid uses >> of character arrays that are not nul-terminated, such as arguments >> to functions that expect a (nul-terminated) string. For example: >> >> char *p = (char*)malloc (20); >> memcpy (p, "/tmp/", 5); >> strcat (p, "file.text"); // << warn here >> >> It would be helpful to diagnose such cases (while avoiding false >> positives on the indeterminate cases you mention, of course). > > One thing here is that there is a function known to require a null > terminated function, not arbitrary other function that may or might not > need it. Understood. GCC knows about a subset of those functions but there is no mechanism to let it know about user-defined functions that have the same constraint. With the warning implemented, adding an attribute would make it possible for GCC to diagnose this problem in general. For instance, say the attribute is called string, libc could annotate fopen like so: FILE* __attribute__ ((string (1), string (2))) fopen (const char *restrict, const char *restrict); > And another thing is that in the tree-ssa-strlen.c framework known > records can be invalidated at any time and you then don't know, > it is an optimization, not a warning framework. > So, for the warning you'd need to track whether there have been any > invalidation and just punt in that case. Sure. Martin
Jakub Jelinek <jakub@redhat.com> writes: > On Fri, May 05, 2017 at 01:01:08PM +0100, Richard Sandiford wrote: >> tree-ssa-strlen.c looks for cases in which a string is built up using >> operations like: >> >> memcpy (a, "foo", 4); >> memcpy (a + 3, "bar", 4); >> int x = strlen (a); >> >> As a side-effect, it optimises the non-final memcpys so that they don't >> include the nul terminator. >> >> However, after removing some "& ~0x1"s from tree-ssa-dse.c, the DSE pass >> does this optimisation itself (because it can tell that later memcpys >> overwrite the terminators). The strlen pass wasn't able to handle these >> pre-optimised calls in the same way as the unoptimised ones. >> >> This patch adds support for tracking unterminated strings. > > I'm not sure I like the terminology (terminated vs. !terminated), I wonder > if it wouldn't be better to add next to length field minimum_length field, > length would be what it is now, tree representing the string length, > while minimum_length would be just a guarantee that strlen (ptr) >= > minimum_length, i.e. that in the first minimum_length bytes (best would be > to guarantee that it is just a constant if non-NULL) are non-zero. > It shouldn't be handled just by non-zero terminated memcpy, but e.g. even if > you e.g. construct it byte by byte, etc. > a[0] = 'a'; > a[1] = 'b'; > a[2] = 'c'; > a[3] = 'd'; > a[4] = '\0'; > x = strlen (a); > etc., or > strcpy (a, "abcdefg"); > strcpy (a + 8, "hijk"); > a[7] = 'q'; > x = strlen (a); > or say by storing 4 non-zero bytes at a time... I've got most of the way through a version that uses min_length instead. But one thing that the terminated flag allows that a constant min_length doesn't is: size_t f1 (char *a1) { size_t x = strlen (a1); char *a3 = a1 + x; a3[0] = '1'; // a1 length x + 1, unterminated (min length x + 1) a3[1] = '2'; // a1 length x + 2, unterminated (min length x + 2) a3[2] = '3'; // a1 length x + 3, unterminated (min length x + 3) a3[3] = 0; // a1 length x + 3, terminated return strlen (a1); } For the a3[3] = 0, we know a3's min_length is 3 and so it's obvious that we can convert its min_length to a length. But even if we allow a1's min_length to be nonconstant, it seems a bit risky to assume that we can convert its min_length to a length as well. It would only work if the min_lengths in related strinfos are kept in sync, whereas it ought to be safe to say that the minimum length of something is 0. Having two separate fields could allow us to say that a1's length is x and its minimum length is 3 in: a1[0] = '1'; a1[1] = '2'; a1[2] = '3'; size_t x = strlen (a1); which in turn would allow the final length of a1 in: a1[0] = '1'; a1[1] = '2'; a1[2] = '3'; size_t x = strlen (a1); a1[3] = '4'; // drop a1's length here a1[4] = 0; to be optimised to 4. But we'd then have to drop the constant minimum for: a1[0] = '1'; a1[1] = '2'; a1[2] = '3'; size_t x = strlen (a1); char *a3 = a1 + x; a3[0] = '4'; // a1's min_length is x + 1, not 4 in order to support: a3[1] = 0; // a1's length is x + 1 even though the minimum of 4 would be correct. So there will be very few cases in which length is not null and not equal to min_length. Maybe we could keep both pieces of information around if we had both a terminated flag and a constant mininum length. So I think that gives four possiblities: (1) Keep the terminated flag, but extend the original patch to handle strings built up a character at a time. This would handle f1 above. (2) Replace the terminated flag with a constant minimum length, don't handle f1 above. (3) Replace the terminated flag with an arbitrary minimum length and ensure that it's always valid to copy the minimum length to the length when we do so for the final strinfo in a chain. (4) Keep the terminated flag and also add a constant minimum length. This would handle all the cases above. Thanks, Richard
Hi! Note the intent of the pass is to handle the most common cases, it is fine if some cases that aren't common aren't handled, it is all about the extra complexity vs. how much it helps on real-world code. On Sun, May 07, 2017 at 10:10:48AM +0100, Richard Sandiford wrote: > I've got most of the way through a version that uses min_length instead. > But one thing that the terminated flag allows that a constant min_length > doesn't is: > > size_t > f1 (char *a1) > { > size_t x = strlen (a1); > char *a3 = a1 + x; > a3[0] = '1'; // a1 length x + 1, unterminated (min length x + 1) > a3[1] = '2'; // a1 length x + 2, unterminated (min length x + 2) > a3[2] = '3'; // a1 length x + 3, unterminated (min length x + 3) > a3[3] = 0; // a1 length x + 3, terminated > return strlen (a1); > } > > For the a3[3] = 0, we know a3's min_length is 3 and so it's obvious > that we can convert its min_length to a length. But even if we allow > a1's min_length to be nonconstant, it seems a bit risky to assume that > we can convert its min_length to a length as well. It would only work > if the min_lengths in related strinfos are kept in sync, whereas it > ought to be safe to say that the minimum length of something is 0. And we have code for that. If verify_related_strinfos returns non-NULL, we can adjust all the related strinfos that need adjusting. See e.g. zero_length_string on how it uses that. It is just that we should decide what is the acceptable complexity of the length/min_length expressions (whether INTEGER_CST or SSA_NAME is enough, then the above would not work, but is that really that important), or if we e.g. allow SSA_NAME + INTEGER_CST in addition to that, or sum of 2 SSA_NAMEs, etc.). I don't see how terminated vs. unterminated (which is misnamed anyway, it means that it isn't known to be terminated, it might be terminated or not) would help with that. > So I think that gives four possiblities: > > (1) Keep the terminated flag, but extend the original patch to handle > strings built up a character at a time. This would handle f1 above. Only if you allow complex expressions like SSA_NAME + INTEGER_CST in length. > (2) Replace the terminated flag with a constant minimum length, don't > handle f1 above. Sure, if you only allow constants, it will be limited to constants. > (3) Replace the terminated flag with an arbitrary minimum length and > ensure that it's always valid to copy the minimum length to the > length when we do so for the final strinfo in a chain. Even length doesn't allow arbitrary expressions, the more complex it is, the more expensive will it be to compute it when you e.g. replace strlen with that. I'd introduce min_length, start with INTEGER_CST, once it is handled everywhere in the pass properly, see if there is enough code in the wild that would justify allowing more than that. min_length is a simple guarantee that there are no zero bytes among the first min_length bytes, length is the same plus that there is a zero byte right after that, so it is easy to argue about what happens if you store non-zero somewhere into it, or store zero, etc. Jakub
Jakub Jelinek <jakub@redhat.com> writes: > Hi! > > Note the intent of the pass is to handle the most common cases, it is fine > if some cases that aren't common aren't handled, it is all about the extra > complexity vs. how much it helps on real-world code. OK. > On Sun, May 07, 2017 at 10:10:48AM +0100, Richard Sandiford wrote: >> I've got most of the way through a version that uses min_length instead. >> But one thing that the terminated flag allows that a constant min_length >> doesn't is: >> >> size_t >> f1 (char *a1) >> { >> size_t x = strlen (a1); >> char *a3 = a1 + x; >> a3[0] = '1'; // a1 length x + 1, unterminated (min length x + 1) >> a3[1] = '2'; // a1 length x + 2, unterminated (min length x + 2) >> a3[2] = '3'; // a1 length x + 3, unterminated (min length x + 3) >> a3[3] = 0; // a1 length x + 3, terminated >> return strlen (a1); >> } >> >> For the a3[3] = 0, we know a3's min_length is 3 and so it's obvious >> that we can convert its min_length to a length. But even if we allow >> a1's min_length to be nonconstant, it seems a bit risky to assume that >> we can convert its min_length to a length as well. It would only work >> if the min_lengths in related strinfos are kept in sync, whereas it >> ought to be safe to say that the minimum length of something is 0. > > And we have code for that. If verify_related_strinfos returns non-NULL, > we can adjust all the related strinfos that need adjusting. > See e.g. zero_length_string on how it uses that. It is just that we should > decide what is the acceptable complexity of the length/min_length > expressions (whether INTEGER_CST or SSA_NAME is enough, then the above > would not work, but is that really that important), or if we e.g. allow > SSA_NAME + INTEGER_CST in addition to that, or sum of 2 SSA_NAMEs, etc.). > I don't see how terminated vs. unterminated (which is misnamed anyway, it > means that it isn't known to be terminated, it might be terminated or not) > would help with that. The example above works with the flag because we already allow SSA_NAME + INTEGER_CST for the length field, thanks to: tree adj = NULL_TREE; if (oldlen == NULL_TREE) ; else if (integer_zerop (oldlen)) adj = srclen; else if (TREE_CODE (oldlen) == INTEGER_CST || TREE_CODE (srclen) == INTEGER_CST) adj = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (srclen), srclen, fold_convert_loc (loc, TREE_TYPE (srclen), oldlen)); if (adj != NULL_TREE) adjust_related_strinfos (loc, dsi, adj); etc. So with a constant min_length we lose out (compared to the flag) by making min_length more restrictive. Like you say later, min_length is the number of characters that are known to be nonzero, and length is the number of characters that are known to be nonzero and followed by a zero, so even if we do relax the rules for min_length to match length, I think in almost all useful cases the length will be equal to the min_length or will be null (i.e. it'll act almost like a de facto flag). If the name's a problem, how about "known_terminated_p" instead of "terminated_p"? >> So I think that gives four possiblities: >> >> (1) Keep the terminated flag, but extend the original patch to handle >> strings built up a character at a time. This would handle f1 above. > > Only if you allow complex expressions like SSA_NAME + INTEGER_CST in length. > >> (2) Replace the terminated flag with a constant minimum length, don't >> handle f1 above. > > Sure, if you only allow constants, it will be limited to constants. > >> (3) Replace the terminated flag with an arbitrary minimum length and >> ensure that it's always valid to copy the minimum length to the >> length when we do so for the final strinfo in a chain. > > Even length doesn't allow arbitrary expressions, the more complex it is, > the more expensive will it be to compute it when you e.g. replace > strlen with that. > > I'd introduce min_length, start with INTEGER_CST, once it is handled > everywhere in the pass properly, see if there is enough code in the wild > that would justify allowing more than that. > > min_length is a simple guarantee that there are no zero bytes among the > first min_length bytes, length is the same plus that there is a zero byte > right after that, so it is easy to argue about what happens if you store > non-zero somewhere into it, or store zero, etc. I think that's true of the flag version too though. If you store a zero into X <= length, you set the length to X and set known_terminated_p. If you store a nonzero into X < length, nothing changes. If you store an unknown value into X < length, you set the length to X and clear the known_terminated_p flag. Thanks, Richard
Richard Sandiford <richard.sandiford@linaro.org> writes: > Jakub Jelinek <jakub@redhat.com> writes: >> Hi! >> >> Note the intent of the pass is to handle the most common cases, it is fine >> if some cases that aren't common aren't handled, it is all about the extra >> complexity vs. how much it helps on real-world code. > > OK. > >> On Sun, May 07, 2017 at 10:10:48AM +0100, Richard Sandiford wrote: >>> I've got most of the way through a version that uses min_length instead. >>> But one thing that the terminated flag allows that a constant min_length >>> doesn't is: >>> >>> size_t >>> f1 (char *a1) >>> { >>> size_t x = strlen (a1); >>> char *a3 = a1 + x; >>> a3[0] = '1'; // a1 length x + 1, unterminated (min length x + 1) >>> a3[1] = '2'; // a1 length x + 2, unterminated (min length x + 2) >>> a3[2] = '3'; // a1 length x + 3, unterminated (min length x + 3) >>> a3[3] = 0; // a1 length x + 3, terminated >>> return strlen (a1); >>> } >>> >>> For the a3[3] = 0, we know a3's min_length is 3 and so it's obvious >>> that we can convert its min_length to a length. But even if we allow >>> a1's min_length to be nonconstant, it seems a bit risky to assume that >>> we can convert its min_length to a length as well. It would only work >>> if the min_lengths in related strinfos are kept in sync, whereas it >>> ought to be safe to say that the minimum length of something is 0. >> >> And we have code for that. If verify_related_strinfos returns non-NULL, >> we can adjust all the related strinfos that need adjusting. >> See e.g. zero_length_string on how it uses that. It is just that we should >> decide what is the acceptable complexity of the length/min_length >> expressions (whether INTEGER_CST or SSA_NAME is enough, then the above >> would not work, but is that really that important), or if we e.g. allow >> SSA_NAME + INTEGER_CST in addition to that, or sum of 2 SSA_NAMEs, etc.). >> I don't see how terminated vs. unterminated (which is misnamed anyway, it >> means that it isn't known to be terminated, it might be terminated or not) >> would help with that. > > The example above works with the flag because we already allow > SSA_NAME + INTEGER_CST for the length field, thanks to: > > tree adj = NULL_TREE; > if (oldlen == NULL_TREE) > ; > else if (integer_zerop (oldlen)) > adj = srclen; > else if (TREE_CODE (oldlen) == INTEGER_CST > || TREE_CODE (srclen) == INTEGER_CST) > adj = fold_build2_loc (loc, MINUS_EXPR, > TREE_TYPE (srclen), srclen, > fold_convert_loc (loc, TREE_TYPE (srclen), > oldlen)); > if (adj != NULL_TREE) > adjust_related_strinfos (loc, dsi, adj); > > etc. So with a constant min_length we lose out (compared to the flag) > by making min_length more restrictive. > > Like you say later, min_length is the number of characters that are > known to be nonzero, and length is the number of characters that are > known to be nonzero and followed by a zero, so even if we do relax the > rules for min_length to match length, I think in almost all useful cases > the length will be equal to the min_length or will be null (i.e. it'll > act almost like a de facto flag). How about the patch below? It renames "length" to "nonzero_chars" and adds a "full_string_p" flag to indicate that the nonzero characters are known to be followed by a zero. It keeps the current decisions about which kinds of length/nonzero_chars expression are valid and worth tracking. It also handles strings built up a character at a time (unlike the original). Tested on aarch64-linux-gnu and x86_64-linux-gnu. Thanks, Richard 2017-05-17 Richard Sandiford <richard.sandiford@linaro.org> gcc/ * tree-ssa-strlen.c (strinfo): Rename the length field to nonzero_chars. Add a full_string_p field. (compare_nonzero_chars, zero_length_string_p): New functions. (get_addr_stridx): Add an offset_out parameter. Use compare_nonzero_chars. (get_stridx): Update accordingly. Use compare_nonzero_chars. (new_strinfo): Update after above changes to strinfo. (set_endptr_and_length): Set full_string_p. (get_string_length): Update after above changes to strinfo. (unshare_strinfo): Update call to new_strinfo. (maybe_invalidate): Likewise. (get_stridx_plus_constant): Change off to unsigned HOST_WIDE_INT. Use compare_nonzero_chars and zero_string_p. Treat nonzero_chars as a uhwi instead of an shwi. Update after above changes to strinfo and new_strinfo. (zero_length_string): Assert that chainsi contains full strings. Use zero_length_string_p. Update call to new_strinfo. (adjust_related_strinfos): Update after above changes to strinfo. Copy full_string_p from origsi. (adjust_last_stmt): Use zero_length_string_p. (handle_builtin_strlen): Update after above changes to strinfo and new_strinfo. Install the lhs as the string length if the previous entry didn't describe a full string. (handle_builtin_strchr): Update after above changes to strinfo and new_strinfo. (handle_builtin_strcpy): Likewise. (handle_builtin_strcat): Likewise. (handle_builtin_malloc): Likewise. (handle_pointer_plus): Likewise. (handle_builtin_memcpy): Likewise. Track nonzero characters that aren't necessarily followed by a nul terminator. (handle_char_store): Likewise. gcc/testsuite/ * gcc.dg/strlenopt-32.c: New testcase. * gcc.dg/strlenopt-33.c: Likewise. * gcc.dg/strlenopt-33g.c: Likewise. * gcc.dg/strlenopt-34.c: Likewise. * gcc.dg/strlenopt-35.c: Likewise.Index: gcc/tree-ssa-strlen.c =================================================================== --- gcc/tree-ssa-strlen.c 2017-05-17 07:33:01.091940890 +0100 +++ gcc/tree-ssa-strlen.c 2017-05-17 07:33:03.918870380 +0100 @@ -57,8 +57,13 @@ the Free Software Foundation; either ver /* String information record. */ struct strinfo { - /* String length of this string. */ - tree length; + /* Number of leading characters that are known to be nonzero. This is + also the length of the string if FULL_STRING_P. + + The values in a list of related string pointers must be consistent; + that is, if strinfo B comes X bytes after strinfo A, it must be + the case that A->nonzero_chars == X + B->nonzero_chars. */ + tree nonzero_chars; /* Any of the corresponding pointers for querying alias oracle. */ tree ptr; /* This is used for two things: @@ -105,6 +110,10 @@ struct strinfo /* A flag for the next maybe_invalidate that this strinfo shouldn't be invalidated. Always cleared by maybe_invalidate. */ bool dont_invalidate; + /* True if the string is known to be nul-terminated after NONZERO_CHARS + characters. False is useful when detecting strings that are built + up via successive memcpys. */ + bool full_string_p; }; /* Pool for allocating strinfo_struct entries. */ @@ -150,7 +159,34 @@ struct laststmt_struct int stridx; } laststmt; -static int get_stridx_plus_constant (strinfo *, HOST_WIDE_INT, tree); +static int get_stridx_plus_constant (strinfo *, unsigned HOST_WIDE_INT, tree); + +/* Return: + + - 1 if SI is known to start with more than OFF nonzero characters. + + - 0 if SI is known to start with OFF nonzero characters, + but is not known to start with more. + + - -1 if SI might not start with OFF nonzero characters. */ + +static inline int +compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off) +{ + if (si->nonzero_chars + && TREE_CODE (si->nonzero_chars) == INTEGER_CST) + return compare_tree_int (si->nonzero_chars, off); + else + return -1; +} + +/* Return true if SI is known to be a zero-length string. */ + +static inline bool +zero_length_string_p (strinfo *si) +{ + return si->full_string_p && integer_zerop (si->nonzero_chars); +} /* Return strinfo vector entry IDX. */ @@ -175,10 +211,13 @@ get_next_strinfo (strinfo *si) return nextsi; } -/* Helper function for get_stridx. */ +/* Helper function for get_stridx. Return the strinfo index of the address + of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is + OK to return the index for some X <= &EXP and store &EXP - X in + *OFFSET_OUT. */ static int -get_addr_stridx (tree exp, tree ptr) +get_addr_stridx (tree exp, tree ptr, unsigned HOST_WIDE_INT *offset_out) { HOST_WIDE_INT off; struct stridxlist *list, *last = NULL; @@ -198,7 +237,11 @@ get_addr_stridx (tree exp, tree ptr) do { if (list->offset == off) - return list->idx; + { + if (offset_out) + *offset_out = 0; + return list->idx; + } if (list->offset > off) return 0; last = list; @@ -206,14 +249,21 @@ get_addr_stridx (tree exp, tree ptr) } while (list); - if (ptr && last && last->idx > 0) + if ((offset_out || ptr) && last && last->idx > 0) { + unsigned HOST_WIDE_INT rel_off + = (unsigned HOST_WIDE_INT) off - last->offset; strinfo *si = get_strinfo (last->idx); - if (si - && si->length - && TREE_CODE (si->length) == INTEGER_CST - && compare_tree_int (si->length, off - last->offset) != -1) - return get_stridx_plus_constant (si, off - last->offset, ptr); + if (si && compare_nonzero_chars (si, rel_off) >= 0) + { + if (offset_out) + { + *offset_out = rel_off; + return last->idx; + } + else + return get_stridx_plus_constant (si, rel_off, ptr); + } } return 0; } @@ -253,10 +303,7 @@ get_stridx (tree exp) { strinfo *si = get_strinfo (ssa_ver_to_stridx[SSA_NAME_VERSION (rhs1)]); - if (si - && si->length - && TREE_CODE (si->length) == INTEGER_CST - && compare_tree_int (si->length, off) != -1) + if (si && compare_nonzero_chars (si, off) >= 0) return get_stridx_plus_constant (si, off, exp); } e = rhs1; @@ -266,7 +313,7 @@ get_stridx (tree exp) if (TREE_CODE (exp) == ADDR_EXPR) { - int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp); + int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp, NULL); if (idx != 0) return idx; } @@ -419,10 +466,10 @@ new_addr_stridx (tree exp) /* Create a new strinfo. */ static strinfo * -new_strinfo (tree ptr, int idx, tree length) +new_strinfo (tree ptr, int idx, tree nonzero_chars, bool full_string_p) { strinfo *si = strinfo_pool.allocate (); - si->length = length; + si->nonzero_chars = nonzero_chars; si->ptr = ptr; si->stmt = NULL; si->endptr = NULL_TREE; @@ -433,6 +480,7 @@ new_strinfo (tree ptr, int idx, tree len si->next = 0; si->writable = false; si->dont_invalidate = false; + si->full_string_p = full_string_p; return si; } @@ -492,8 +540,9 @@ set_endptr_and_length (location_t loc, s si->stmt = NULL; tree start_as_size = fold_convert_loc (loc, size_type_node, si->ptr); tree end_as_size = fold_convert_loc (loc, size_type_node, endptr); - si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node, - end_as_size, start_as_size); + si->nonzero_chars = fold_build2_loc (loc, MINUS_EXPR, size_type_node, + end_as_size, start_as_size); + si->full_string_p = true; } /* Return string length, or NULL if it can't be computed. */ @@ -501,8 +550,8 @@ set_endptr_and_length (location_t loc, s static tree get_string_length (strinfo *si) { - if (si->length) - return si->length; + if (si->nonzero_chars) + return si->full_string_p ? si->nonzero_chars : NULL; if (si->stmt) { @@ -595,19 +644,19 @@ get_string_length (strinfo *si) for (strinfo *chainsi = verify_related_strinfos (si); chainsi != NULL; chainsi = get_next_strinfo (chainsi)) - if (chainsi->length == NULL) + if (chainsi->nonzero_chars == NULL) set_endptr_and_length (loc, chainsi, lhs); break; case BUILT_IN_MALLOC: break; - /* BUILT_IN_CALLOC always has si->length set. */ + /* BUILT_IN_CALLOC always has si->nonzero_chars set. */ default: gcc_unreachable (); break; } } - return si->length; + return si->nonzero_chars; } /* Invalidate string length information for strings whose length @@ -626,7 +675,7 @@ maybe_invalidate (gimple *stmt) if (!si->dont_invalidate) { ao_ref r; - /* Do not use si->length. */ + /* Do not use si->nonzero_chars. */ ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE); if (stmt_may_clobber_ref_p_1 (stmt, &r)) { @@ -653,7 +702,7 @@ unshare_strinfo (strinfo *si) if (si->refcount == 1 && !strinfo_shared ()) return si; - nsi = new_strinfo (si->ptr, si->idx, si->length); + nsi = new_strinfo (si->ptr, si->idx, si->nonzero_chars, si->full_string_p); nsi->stmt = si->stmt; nsi->endptr = si->endptr; nsi->first = si->first; @@ -670,39 +719,39 @@ unshare_strinfo (strinfo *si) been created. */ static int -get_stridx_plus_constant (strinfo *basesi, HOST_WIDE_INT off, tree ptr) +get_stridx_plus_constant (strinfo *basesi, unsigned HOST_WIDE_INT off, + tree ptr) { if (TREE_CODE (ptr) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr)) return 0; - if (basesi->length == NULL_TREE - || TREE_CODE (basesi->length) != INTEGER_CST - || compare_tree_int (basesi->length, off) == -1 - || !tree_fits_shwi_p (basesi->length)) + if (compare_nonzero_chars (basesi, off) < 0 + || !tree_fits_uhwi_p (basesi->nonzero_chars)) return 0; - HOST_WIDE_INT len = tree_to_shwi (basesi->length) - off; + unsigned HOST_WIDE_INT nonzero_chars + = tree_to_uhwi (basesi->nonzero_chars) - off; strinfo *si = basesi, *chainsi; if (si->first || si->prev || si->next) si = verify_related_strinfos (basesi); if (si == NULL - || si->length == NULL_TREE - || TREE_CODE (si->length) != INTEGER_CST) + || si->nonzero_chars == NULL_TREE + || TREE_CODE (si->nonzero_chars) != INTEGER_CST) return 0; if (TREE_CODE (ptr) == SSA_NAME && ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr)) ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names); - gcc_checking_assert (compare_tree_int (si->length, off) != -1); + gcc_checking_assert (compare_tree_int (si->nonzero_chars, off) != -1); for (chainsi = si; chainsi->next; chainsi = si) { si = get_next_strinfo (chainsi); if (si == NULL - || si->length == NULL_TREE - || TREE_CODE (si->length) != INTEGER_CST) + || si->nonzero_chars == NULL_TREE + || TREE_CODE (si->nonzero_chars) != INTEGER_CST) break; - int r = compare_tree_int (si->length, len); + int r = compare_tree_int (si->nonzero_chars, nonzero_chars); if (r != 1) { if (r == 0) @@ -724,7 +773,8 @@ get_stridx_plus_constant (strinfo *bases int idx = new_stridx (ptr); if (idx == 0) return 0; - si = new_strinfo (ptr, idx, build_int_cst (size_type_node, len)); + si = new_strinfo (ptr, idx, build_int_cst (size_type_node, nonzero_chars), + basesi->full_string_p); set_strinfo (idx, si); if (chainsi->next) { @@ -736,7 +786,7 @@ get_stridx_plus_constant (strinfo *bases if (chainsi->first == 0) chainsi->first = chainsi->idx; chainsi->next = idx; - if (chainsi->endptr == NULL_TREE && len == 0) + if (chainsi->endptr == NULL_TREE && zero_length_string_p (si)) chainsi->endptr = ptr; si->endptr = chainsi->endptr; si->prev = chainsi->idx; @@ -769,7 +819,7 @@ zero_length_string (tree ptr, strinfo *c do { /* We shouldn't mix delayed and non-delayed lengths. */ - gcc_assert (si->length); + gcc_assert (si->full_string_p); if (si->endptr == NULL_TREE) { si = unshare_strinfo (si); @@ -779,7 +829,7 @@ zero_length_string (tree ptr, strinfo *c si = get_next_strinfo (si); } while (si != NULL); - if (chainsi->length && integer_zerop (chainsi->length)) + if (zero_length_string_p (chainsi)) { if (chainsi->next) { @@ -793,7 +843,7 @@ zero_length_string (tree ptr, strinfo *c else { /* We shouldn't mix delayed and non-delayed lengths. */ - gcc_assert (chainsi->length); + gcc_assert (chainsi->full_string_p); if (chainsi->first || chainsi->prev || chainsi->next) { chainsi = unshare_strinfo (chainsi); @@ -806,7 +856,7 @@ zero_length_string (tree ptr, strinfo *c idx = new_stridx (ptr); if (idx == 0) return NULL; - si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0)); + si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0), true); set_strinfo (idx, si); si->endptr = ptr; if (chainsi != NULL) @@ -824,9 +874,11 @@ zero_length_string (tree ptr, strinfo *c return si; } -/* For strinfo ORIGSI whose length has been just updated - update also related strinfo lengths (add ADJ to each, - but don't adjust ORIGSI). */ +/* For strinfo ORIGSI whose length has been just updated, adjust other + related strinfos so that they match the new ORIGSI. This involves: + + - adding ADJ to the nonzero_chars fields + - copying full_string_p from the new ORIGSI. */ static void adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj) @@ -848,10 +900,12 @@ adjust_related_strinfos (location_t loc, /* We shouldn't see delayed lengths here; the caller must have calculated the old length in order to calculate the adjustment. */ - gcc_assert (si->length); - tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj); - si->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (si->length), - si->length, tem); + gcc_assert (si->nonzero_chars); + tem = fold_convert_loc (loc, TREE_TYPE (si->nonzero_chars), adj); + si->nonzero_chars = fold_build2_loc (loc, PLUS_EXPR, + TREE_TYPE (si->nonzero_chars), + si->nonzero_chars, tem); + si->full_string_p = origsi->full_string_p; si->endptr = NULL_TREE; si->dont_invalidate = true; @@ -1020,11 +1074,8 @@ adjust_last_stmt (strinfo *si, gimple *s } } - if (!is_strcat) - { - if (si->length == NULL_TREE || !integer_zerop (si->length)) - return; - } + if (!is_strcat && !zero_length_string_p (si)) + return; if (is_gimple_assign (last.stmt)) { @@ -1138,12 +1189,13 @@ handle_builtin_strlen (gimple_stmt_itera print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } if (si != NULL - && TREE_CODE (si->length) != SSA_NAME - && TREE_CODE (si->length) != INTEGER_CST + && TREE_CODE (si->nonzero_chars) != SSA_NAME + && TREE_CODE (si->nonzero_chars) != INTEGER_CST && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) { si = unshare_strinfo (si); - si->length = lhs; + si->nonzero_chars = lhs; + gcc_assert (si->full_string_p); } return; } @@ -1152,11 +1204,25 @@ handle_builtin_strlen (gimple_stmt_itera return; if (idx == 0) idx = new_stridx (src); - else if (get_strinfo (idx) != NULL) - return; + else + { + strinfo *si = get_strinfo (idx); + if (si != NULL) + { + if (!si->full_string_p && !si->stmt) + { + /* Until now we only had a lower bound on the string length. + Install LHS as the actual length. */ + si = unshare_strinfo (si); + si->nonzero_chars = lhs; + si->full_string_p = true; + } + return; + } + } if (idx) { - strinfo *si = new_strinfo (src, idx, lhs); + strinfo *si = new_strinfo (src, idx, lhs, true); set_strinfo (idx, si); find_equal_ptrs (src, idx); } @@ -1260,7 +1326,7 @@ handle_builtin_strchr (gimple_stmt_itera tree srcu = fold_convert_loc (loc, size_type_node, src); tree length = fold_build2_loc (loc, MINUS_EXPR, size_type_node, lhsu, srcu); - strinfo *si = new_strinfo (src, idx, length); + strinfo *si = new_strinfo (src, idx, length, true); si->endptr = lhs; set_strinfo (idx, si); find_equal_ptrs (src, idx); @@ -1349,9 +1415,10 @@ handle_builtin_strcpy (enum built_in_fun } if (olddsi != NULL) { - oldlen = olddsi->length; + oldlen = olddsi->nonzero_chars; dsi = unshare_strinfo (olddsi); - dsi->length = srclen; + dsi->nonzero_chars = srclen; + dsi->full_string_p = (srclen != NULL_TREE); /* Break the chain, so adjust_related_strinfo on later pointers in the chain won't adjust this one anymore. */ dsi->next = 0; @@ -1360,14 +1427,14 @@ handle_builtin_strcpy (enum built_in_fun } else { - dsi = new_strinfo (dst, didx, srclen); + dsi = new_strinfo (dst, didx, srclen, srclen != NULL_TREE); set_strinfo (didx, dsi); find_equal_ptrs (dst, didx); } dsi->writable = true; dsi->dont_invalidate = true; - if (dsi->length == NULL_TREE) + if (dsi->nonzero_chars == NULL_TREE) { strinfo *chainsi; @@ -1388,7 +1455,8 @@ handle_builtin_strcpy (enum built_in_fun invalidated. */ chainsi = unshare_strinfo (chainsi); chainsi->stmt = stmt; - chainsi->length = NULL_TREE; + chainsi->nonzero_chars = NULL_TREE; + chainsi->full_string_p = false; chainsi->endptr = NULL_TREE; chainsi->dont_invalidate = true; } @@ -1556,31 +1624,61 @@ handle_builtin_memcpy (enum built_in_fun && !integer_zerop (len)) adjust_last_stmt (olddsi, stmt, false); + bool full_string_p; if (idx > 0) { gimple *def_stmt; - /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */ + /* Handle memcpy (x, y, l) where l's relationship with strlen (y) + is known. */ si = get_strinfo (idx); - if (si == NULL || si->length == NULL_TREE) - return; - if (TREE_CODE (len) != SSA_NAME) - return; - def_stmt = SSA_NAME_DEF_STMT (len); - if (!is_gimple_assign (def_stmt) - || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR - || gimple_assign_rhs1 (def_stmt) != si->length - || !integer_onep (gimple_assign_rhs2 (def_stmt))) + if (si == NULL || si->nonzero_chars == NULL_TREE) return; + if (TREE_CODE (len) == INTEGER_CST + && TREE_CODE (si->nonzero_chars) == INTEGER_CST) + { + if (tree_int_cst_le (len, si->nonzero_chars)) + { + /* Copying LEN nonzero characters, where LEN is constant. */ + newlen = len; + full_string_p = false; + } + else + { + /* Copying the whole of the analyzed part of SI. */ + newlen = si->nonzero_chars; + full_string_p = si->full_string_p; + } + } + else + { + if (!si->full_string_p) + return; + if (TREE_CODE (len) != SSA_NAME) + return; + def_stmt = SSA_NAME_DEF_STMT (len); + if (!is_gimple_assign (def_stmt) + || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR + || gimple_assign_rhs1 (def_stmt) != si->nonzero_chars + || !integer_onep (gimple_assign_rhs2 (def_stmt))) + return; + /* Copying variable-length string SI (and no more). */ + newlen = si->nonzero_chars; + full_string_p = true; + } } else { si = NULL; /* Handle memcpy (x, "abcd", 5) or memcpy (x, "abc\0uvw", 7). */ - if (!tree_fits_uhwi_p (len) - || tree_to_uhwi (len) <= (unsigned HOST_WIDE_INT) ~idx) + if (!tree_fits_uhwi_p (len)) return; + + unsigned HOST_WIDE_INT clen = tree_to_uhwi (len); + unsigned HOST_WIDE_INT nonzero_chars = ~idx; + newlen = build_int_cst (size_type_node, MIN (nonzero_chars, clen)); + full_string_p = clen > nonzero_chars; } if (olddsi != NULL && TREE_CODE (len) == SSA_NAME) @@ -1592,16 +1690,13 @@ handle_builtin_memcpy (enum built_in_fun if (didx == 0) return; } - if (si != NULL) - newlen = si->length; - else - newlen = build_int_cst (size_type_node, ~idx); oldlen = NULL_TREE; if (olddsi != NULL) { dsi = unshare_strinfo (olddsi); - oldlen = olddsi->length; - dsi->length = newlen; + oldlen = olddsi->nonzero_chars; + dsi->nonzero_chars = newlen; + dsi->full_string_p = full_string_p; /* Break the chain, so adjust_related_strinfo on later pointers in the chain won't adjust this one anymore. */ dsi->next = 0; @@ -1610,7 +1705,7 @@ handle_builtin_memcpy (enum built_in_fun } else { - dsi = new_strinfo (dst, didx, newlen); + dsi = new_strinfo (dst, didx, newlen, full_string_p); set_strinfo (didx, dsi); find_equal_ptrs (dst, didx); } @@ -1623,12 +1718,11 @@ handle_builtin_memcpy (enum built_in_fun if (oldlen == NULL_TREE) ; else if (integer_zerop (oldlen)) - adj = dsi->length; + adj = newlen; else if (TREE_CODE (oldlen) == INTEGER_CST - || TREE_CODE (dsi->length) == INTEGER_CST) - adj = fold_build2_loc (loc, MINUS_EXPR, - TREE_TYPE (dsi->length), dsi->length, - fold_convert_loc (loc, TREE_TYPE (dsi->length), + || TREE_CODE (newlen) == INTEGER_CST) + adj = fold_build2_loc (loc, MINUS_EXPR, TREE_TYPE (newlen), newlen, + fold_convert_loc (loc, TREE_TYPE (newlen), oldlen)); if (adj != NULL_TREE) adjust_related_strinfos (loc, dsi, adj); @@ -1640,27 +1734,30 @@ handle_builtin_memcpy (enum built_in_fun if (si != NULL) si->dont_invalidate = true; - lhs = gimple_call_lhs (stmt); - switch (bcode) + if (full_string_p) { - case BUILT_IN_MEMCPY: - case BUILT_IN_MEMCPY_CHK: - case BUILT_IN_MEMCPY_CHKP: - case BUILT_IN_MEMCPY_CHK_CHKP: - /* Allow adjust_last_stmt to decrease this memcpy's size. */ - laststmt.stmt = stmt; - laststmt.len = dsi->length; - laststmt.stridx = dsi->idx; - if (lhs) - ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; - break; - case BUILT_IN_MEMPCPY: - case BUILT_IN_MEMPCPY_CHK: - case BUILT_IN_MEMPCPY_CHKP: - case BUILT_IN_MEMPCPY_CHK_CHKP: - break; - default: - gcc_unreachable (); + lhs = gimple_call_lhs (stmt); + switch (bcode) + { + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMCPY_CHK: + case BUILT_IN_MEMCPY_CHKP: + case BUILT_IN_MEMCPY_CHK_CHKP: + /* Allow adjust_last_stmt to decrease this memcpy's size. */ + laststmt.stmt = stmt; + laststmt.len = dsi->nonzero_chars; + laststmt.stridx = dsi->idx; + if (lhs) + ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; + break; + case BUILT_IN_MEMPCPY: + case BUILT_IN_MEMPCPY_CHK: + case BUILT_IN_MEMPCPY_CHKP: + case BUILT_IN_MEMPCPY_CHK_CHKP: + break; + default: + gcc_unreachable (); + } } } @@ -1709,14 +1806,15 @@ handle_builtin_strcat (enum built_in_fun } if (dsi == NULL) { - dsi = new_strinfo (dst, didx, NULL_TREE); + dsi = new_strinfo (dst, didx, NULL_TREE, false); set_strinfo (didx, dsi); find_equal_ptrs (dst, didx); } else { dsi = unshare_strinfo (dsi); - dsi->length = NULL_TREE; + dsi->nonzero_chars = NULL_TREE; + dsi->full_string_p = false; dsi->next = 0; dsi->endptr = NULL_TREE; } @@ -1740,7 +1838,7 @@ handle_builtin_strcat (enum built_in_fun } loc = gimple_location (stmt); - dstlen = dsi->length; + dstlen = dsi->nonzero_chars; endptr = dsi->endptr; dsi = unshare_strinfo (dsi); @@ -1750,14 +1848,17 @@ handle_builtin_strcat (enum built_in_fun if (srclen != NULL_TREE) { - dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length), - dsi->length, srclen); + dsi->nonzero_chars = fold_build2_loc (loc, PLUS_EXPR, + TREE_TYPE (dsi->nonzero_chars), + dsi->nonzero_chars, srclen); + gcc_assert (dsi->full_string_p); adjust_related_strinfos (loc, dsi, srclen); dsi->dont_invalidate = true; } else { - dsi->length = NULL; + dsi->nonzero_chars = NULL; + dsi->full_string_p = false; if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY)) dsi->dont_invalidate = true; } @@ -1890,7 +1991,7 @@ handle_builtin_malloc (enum built_in_fun tree length = NULL_TREE; if (bcode == BUILT_IN_CALLOC) length = build_int_cst (size_type_node, 0); - strinfo *si = new_strinfo (lhs, idx, length); + strinfo *si = new_strinfo (lhs, idx, length, length != NULL_TREE); if (bcode == BUILT_IN_CALLOC) si->endptr = lhs; set_strinfo (idx, si); @@ -1932,7 +2033,8 @@ handle_builtin_memset (gimple_stmt_itera gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1); update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2, size, build_one_cst (size_type_node)); - si1->length = build_int_cst (size_type_node, 0); + si1->nonzero_chars = build_int_cst (size_type_node, 0); + si1->full_string_p = true; si1->stmt = gsi_stmt (gsi1); } else @@ -2064,18 +2166,20 @@ handle_pointer_plus (gimple_stmt_iterato } si = get_strinfo (idx); - if (si == NULL || si->length == NULL_TREE) + if (si == NULL || si->nonzero_chars == NULL_TREE) return; off = gimple_assign_rhs2 (stmt); zsi = NULL; - if (operand_equal_p (si->length, off, 0)) + if (si->full_string_p && operand_equal_p (si->nonzero_chars, off, 0)) zsi = zero_length_string (lhs, si); else if (TREE_CODE (off) == SSA_NAME) { gimple *def_stmt = SSA_NAME_DEF_STMT (off); if (gimple_assign_single_p (def_stmt) - && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0)) + && si->full_string_p + && operand_equal_p (si->nonzero_chars, + gimple_assign_rhs1 (def_stmt), 0)) zsi = zero_length_string (lhs, si); } if (zsi != NULL @@ -2101,63 +2205,63 @@ handle_char_store (gimple_stmt_iterator strinfo *si = NULL; gimple *stmt = gsi_stmt (*gsi); tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt); + tree rhs = gimple_assign_rhs1 (stmt); + unsigned HOST_WIDE_INT offset = 0; if (TREE_CODE (lhs) == MEM_REF && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME) { - if (integer_zerop (TREE_OPERAND (lhs, 1))) + tree mem_offset = TREE_OPERAND (lhs, 1); + if (tree_fits_uhwi_p (mem_offset)) { - ssaname = TREE_OPERAND (lhs, 0); - idx = get_stridx (ssaname); + /* Get the strinfo for the base, and use it if it starts with at + least OFFSET nonzero characters. This is trivially true if + OFFSET is zero. */ + offset = tree_to_uhwi (mem_offset); + idx = get_stridx (TREE_OPERAND (lhs, 0)); + if (idx > 0) + si = get_strinfo (idx); + if (offset == 0) + ssaname = TREE_OPERAND (lhs, 0); + else if (si == NULL || compare_nonzero_chars (si, offset) < 0) + return true; } } else - idx = get_addr_stridx (lhs, NULL_TREE); + { + idx = get_addr_stridx (lhs, NULL_TREE, &offset); + if (idx > 0) + si = get_strinfo (idx); + } - if (idx > 0) + bool storing_zero_p = initializer_zerop (rhs); + bool storing_nonzero_p = (!storing_zero_p + && TREE_CODE (rhs) == INTEGER_CST + && integer_nonzerop (rhs)); + + if (si != NULL) { - si = get_strinfo (idx); - if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length)) - { - if (initializer_zerop (gimple_assign_rhs1 (stmt))) - { - /* When storing '\0', the store can be removed - if we know it has been stored in the current function. */ - if (!stmt_could_throw_p (stmt) && si->writable) - { - unlink_stmt_vdef (stmt); - release_defs (stmt); - gsi_remove (gsi, true); - return false; - } - else - { - si->writable = true; - gsi_next (gsi); - return false; - } + int cmp = compare_nonzero_chars (si, offset); + gcc_assert (offset == 0 || cmp >= 0); + if (storing_zero_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 (stmt) && si->writable) + { + unlink_stmt_vdef (stmt); + release_defs (stmt); + gsi_remove (gsi, true); + return false; } else - /* Otherwise this statement overwrites the '\0' with - something, if the previous stmt was a memcpy, - its length may be decreased. */ - adjust_last_stmt (si, stmt, false); - } - else if (si != NULL && integer_zerop (gimple_assign_rhs1 (stmt))) - { - si = unshare_strinfo (si); - si->length = build_int_cst (size_type_node, 0); - si->endptr = NULL; - si->prev = 0; - si->next = 0; - si->stmt = NULL; - si->first = 0; - si->writable = true; - if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) - si->endptr = ssaname; - si->dont_invalidate = true; + { + si->writable = true; + gsi_next (gsi); + return false; + } } - /* If si->length is non-zero constant, we aren't overwriting '\0', + /* 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 @@ -2177,35 +2281,74 @@ handle_char_store (gimple_stmt_iterator bar (len, len2, len3, len4); } */ - else if (si != NULL && si->length != NULL_TREE - && TREE_CODE (si->length) == INTEGER_CST - && integer_nonzerop (gimple_assign_rhs1 (stmt))) + else if (storing_nonzero_p && cmp > 0) { gsi_next (gsi); return false; } + else if (storing_zero_p || storing_nonzero_p || (offset != 0 && cmp > 0)) + { + /* When storing_nonzero_p, we know that the string now starts + with OFFSET + 1 nonzero characters, but don't know whether + there's a following nul terminator. + + When storing_zero_p, we know that the string is now OFFSET + characters long. + + Otherwise, we're storing an unknown value at offset OFFSET, + so need to clip the nonzero_chars to OFFSET. */ + location_t loc = gimple_location (stmt); + tree oldlen = si->nonzero_chars; + if (cmp == 0 && si->full_string_p) + /* We're overwriting the nul terminator with a nonzero or + unknown character. If the previous stmt was a memcpy, + its length may be decreased. */ + adjust_last_stmt (si, stmt, false); + si = unshare_strinfo (si); + if (storing_nonzero_p) + si->nonzero_chars = build_int_cst (size_type_node, offset + 1); + else + si->nonzero_chars = build_int_cst (size_type_node, offset); + si->full_string_p = storing_zero_p; + if (storing_zero_p + && ssaname + && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) + si->endptr = ssaname; + else + si->endptr = NULL; + si->next = 0; + si->stmt = NULL; + si->writable = true; + si->dont_invalidate = true; + if (oldlen) + { + tree adj = fold_build2_loc (loc, MINUS_EXPR, size_type_node, + si->nonzero_chars, oldlen); + adjust_related_strinfos (loc, si, adj); + } + else + si->prev = 0; + } } - else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt))) + else if (idx == 0 && (storing_zero_p || storing_nonzero_p)) { if (ssaname) - { - si = zero_length_string (ssaname, NULL); - if (si != NULL) - si->dont_invalidate = true; - } + idx = new_stridx (ssaname); else + idx = new_addr_stridx (lhs); + if (idx != 0) { - int idx = new_addr_stridx (lhs); - if (idx != 0) - { - si = new_strinfo (build_fold_addr_expr (lhs), idx, - build_int_cst (size_type_node, 0)); - set_strinfo (idx, si); - si->dont_invalidate = true; - } + tree ptr = (ssaname ? ssaname : build_fold_addr_expr (lhs)); + tree len = storing_nonzero_p ? size_one_node : size_zero_node; + si = new_strinfo (ptr, idx, len, storing_zero_p); + set_strinfo (idx, si); + if (storing_zero_p + && ssaname + && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) + si->endptr = ssaname; + si->dont_invalidate = true; + si->writable = true; } - if (si != NULL) - si->writable = true; } else if (idx == 0 && TREE_CODE (gimple_assign_rhs1 (stmt)) == STRING_CST @@ -2220,14 +2363,14 @@ handle_char_store (gimple_stmt_iterator if (idx != 0) { si = new_strinfo (build_fold_addr_expr (lhs), idx, - build_int_cst (size_type_node, l)); + build_int_cst (size_type_node, l), true); set_strinfo (idx, si); si->dont_invalidate = true; } } } - if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt))) + if (si != NULL && offset == 0 && storing_zero_p) { /* Allow adjust_last_stmt to remove it if the stored '\0' is immediately overwritten. */ Index: gcc/testsuite/gcc.dg/strlenopt-32.c =================================================================== --- /dev/null 2017-05-16 16:51:34.993412001 +0100 +++ gcc/testsuite/gcc.dg/strlenopt-32.c 2017-05-17 07:33:03.919877480 +0100 @@ -0,0 +1,193 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +char temp[30]; +volatile int v; + +size_t __attribute__ ((noinline, noclone)) +f1 (void) +{ + char a[30]; + v += 1; + memcpy (a, "1234567", 7); + memcpy (a + 7, "89abcdefg", 9); + memcpy (a + 16, "h", 2); + return strlen (a); // This strlen should be optimized into 17. +} + +size_t __attribute__ ((noinline, noclone)) +f2 (char *a) +{ + v += 2; + memcpy (a, "1234567", 7); + memcpy (a + 7, "89abcdefg", 9); + memcpy (a + 16, "h", 2); + return strlen (a); // This strlen should be optimized into 17. +} + +size_t __attribute__ ((noinline, noclone)) +f3 (void) +{ + char a[30]; + v += 3; + a[0] = '1'; + memcpy (a + 1, "2345678", 8); + return strlen (a); // This strlen should be optimized into 8. +} + +size_t __attribute__ ((noinline, noclone)) +f4 (char *a) +{ + v += 4; + a[0] = '1'; + memcpy (a + 1, "2345678", 8); + return strlen (a); // This strlen should be optimized into 8. +} + +size_t __attribute__ ((noinline, noclone)) +f5 (void) +{ + char a[30]; + v += 5; + a[0] = '1'; + a[1] = '2'; + a[2] = '3'; + memcpy (a + 3, "456", 3); + a[6] = '7'; + a[7] = 0; + return strlen (a); // This strlen should be optimized into 7. +} + +size_t __attribute__ ((noinline, noclone)) +f6 (char *a) +{ + v += 6; + a[0] = '1'; + a[1] = '2'; + a[2] = '3'; + memcpy (a + 3, "456", 3); + a[6] = '7'; + a[7] = 0; + return strlen (a); // This strlen should be optimized into 7. +} + +size_t __attribute__ ((noinline, noclone)) +f7 (void) +{ + char a[30]; + v += 7; + strcpy (a, "abcde"); + int len1 = strlen (a); + a[2] = '_'; + int len2 = strlen (a); + return len1 + len2; // This should be optimized into 10. +} + +size_t __attribute__ ((noinline, noclone)) +f8 (char *a) +{ + v += 8; + strcpy (a, "abcde"); + int len1 = strlen (a); + a[2] = '_'; + int len2 = strlen (a); + return len1 + len2; // This should be optimized into 10. +} + +size_t __attribute__ ((noinline, noclone)) +f9 (char b) +{ + char a[30]; + v += 9; + strcpy (a, "foo.bar"); + a[4] = b; + a[3] = 0; + return strlen (a); // This should be optimized into 3. +} + +size_t __attribute__ ((noinline, noclone)) +f10 (char *a, char b) +{ + v += 10; + strcpy (a, "foo.bar"); + a[4] = b; + a[3] = 0; + return strlen (a); // This should be optimized into 3. +} + +size_t __attribute__ ((noinline, noclone)) +f11 (void) +{ + char a[30]; + v += 11; + strcpy (temp, "123456"); + memcpy (a, temp, 7); + return strlen (a); // This should be optimized into 6. +} + +size_t __attribute__ ((noinline, noclone)) +f12 (char *a) +{ + v += 12; + strcpy (temp, "123456"); + memcpy (a, temp, 7); + return strlen (a); // This should be optimized into 6. +} + +size_t __attribute__ ((noinline, noclone)) +f13 (void) +{ + char a[30]; + v += 13; + strcpy (temp, "1234567"); + memcpy (a, temp, 7); + a[7] = 0; + return strlen (a); // This should be optimized into 7. +} + +size_t __attribute__ ((noinline, noclone)) +f14 (char *a) +{ + v += 14; + strcpy (temp, "1234567"); + memcpy (a, temp, 7); + a[7] = 0; + return strlen (a); // This should be optimized into 7. +} + +size_t __attribute__ ((noinline, noclone)) +f15 (void) +{ + char a[30]; + v += 15; + strcpy (temp, "12345679"); + memcpy (a, temp, 7); + a[7] = 0; + return strlen (a); // This should be optimized into 7. +} + +size_t __attribute__ ((noinline, noclone)) +f16 (char *a) +{ + v += 16; + strcpy (temp, "123456789"); + memcpy (a, temp, 7); + a[7] = 0; + return strlen (a); // This should be optimized into 7. +} + +int +main () +{ + char a[30]; + if (f1 () != 17 || f2 (a) != 17 || f3 () != 8 || f4 (a) != 8 + || f5 () != 7 || f6 (a) != 7 || f7 () != 10 || f8 (a) != 10 + || f9 ('_') != 3 || f10 (a, '_') != 3 || f11 () != 6 || f12 (a) != 6 + || f13 () != 7 || f14 (a) != 7 || f15 () != 7 || f16 (a) != 7) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ Index: gcc/testsuite/gcc.dg/strlenopt-33.c =================================================================== --- /dev/null 2017-05-16 16:51:34.993412001 +0100 +++ gcc/testsuite/gcc.dg/strlenopt-33.c 2017-05-17 07:33:03.919877480 +0100 @@ -0,0 +1,42 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +volatile int v; + +size_t __attribute__ ((noinline, noclone)) +f1 (char *b) +{ + char a[30]; + v += 1; + strcpy (a, b); + // This needs to stay. + int len1 = strlen (a); + a[0] = '_'; + a[1] = 0; + return len1 + strlen (a); +} + +size_t __attribute__ ((noinline, noclone)) +f2 (char *a, char *b) +{ + v += 2; + strcpy (a, b); + // This needs to stay. + int len1 = strlen (a); + a[0] = '_'; + a[1] = 0; + return len1 + strlen (a); +} + +int +main () +{ + char a[30]; + if (f1 ("foo") != 4 || f2 (a, "foobar") != 7) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ Index: gcc/testsuite/gcc.dg/strlenopt-33g.c =================================================================== --- /dev/null 2017-05-16 16:51:34.993412001 +0100 +++ gcc/testsuite/gcc.dg/strlenopt-33g.c 2017-05-17 07:33:03.919877480 +0100 @@ -0,0 +1,45 @@ +/* { dg-do run { target *-*-linux* *-*-gnu* } } */ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define USE_GNU +#include "strlenopt.h" + +volatile int v; + +size_t __attribute__ ((noinline, noclone)) +f1 (char *b) +{ + char a[30]; + v += 1; + // Should be converted to stpcpy. + strcpy (a, b); + int len1 = strlen (a); + a[0] = '_'; + a[1] = 0; + return len1 + strlen (a); +} + +size_t __attribute__ ((noinline, noclone)) +f2 (char *a, char *b) +{ + v += 2; + // Should be converted to stpcpy. + strcpy (a, b); + int len1 = strlen (a); + a[0] = '_'; + a[1] = 0; + return len1 + strlen (a); +} + +int +main () +{ + char a[30]; + if (f1 ("foo") != 4 || f2 (a, "foobar") != 7) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 2 "strlen" } } */ Index: gcc/testsuite/gcc.dg/strlenopt-34.c =================================================================== --- /dev/null 2017-05-16 16:51:34.993412001 +0100 +++ gcc/testsuite/gcc.dg/strlenopt-34.c 2017-05-17 07:33:14.155034020 +0100 @@ -0,0 +1,38 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +volatile int v; + +size_t __attribute__ ((noinline, noclone)) +f1 (char b) +{ + char a[30]; + v += 1; + strcpy (a, "foo.bar"); + a[3] = b; + a[4] = 0; + return strlen (a); +} + +size_t __attribute__ ((noinline, noclone)) +f2 (char *a, char b) +{ + v += 2; + strcpy (a, "foo.bar"); + a[3] = b; + a[4] = 0; + return strlen (a); +} + +int +main () +{ + char a[30]; + if (f1 ('_') != 4 || f1 (0) != 3 || f2 (a, '_') != 4 || f2 (a, 0) != 3) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ Index: gcc/testsuite/gcc.dg/strlenopt-35.c =================================================================== --- /dev/null 2017-05-16 16:51:34.993412001 +0100 +++ gcc/testsuite/gcc.dg/strlenopt-35.c 2017-05-17 07:33:03.919877480 +0100 @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +volatile int v; + +size_t +f1 (char *a1) +{ + v += 1; + size_t x = strlen (a1); + char *a2 = a1 + x; + a2[0] = '1'; + a2[1] = '2'; + a2[2] = '3'; + a2[3] = 0; + return strlen (a1); +} + +int +main () +{ + char a[30]; + strcpy (a, "abcd"); + if (f1 (a) != 7) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */
On Wed, May 17, 2017 at 07:52:38AM +0100, Richard Sandiford wrote: > 2017-05-17 Richard Sandiford <richard.sandiford@linaro.org> > > gcc/ > * tree-ssa-strlen.c (strinfo): Rename the length field to > nonzero_chars. Add a full_string_p field. > (compare_nonzero_chars, zero_length_string_p): New functions. > (get_addr_stridx): Add an offset_out parameter. > Use compare_nonzero_chars. > (get_stridx): Update accordingly. Use compare_nonzero_chars. > (new_strinfo): Update after above changes to strinfo. > (set_endptr_and_length): Set full_string_p. > (get_string_length): Update after above changes to strinfo. > (unshare_strinfo): Update call to new_strinfo. > (maybe_invalidate): Likewise. > (get_stridx_plus_constant): Change off to unsigned HOST_WIDE_INT. > Use compare_nonzero_chars and zero_string_p. Treat nonzero_chars > as a uhwi instead of an shwi. Update after above changes to > strinfo and new_strinfo. > (zero_length_string): Assert that chainsi contains full strings. > Use zero_length_string_p. Update call to new_strinfo. > (adjust_related_strinfos): Update after above changes to strinfo. > Copy full_string_p from origsi. > (adjust_last_stmt): Use zero_length_string_p. > (handle_builtin_strlen): Update after above changes to strinfo and > new_strinfo. Install the lhs as the string length if the previous > entry didn't describe a full string. > (handle_builtin_strchr): Update after above changes to strinfo > and new_strinfo. > (handle_builtin_strcpy): Likewise. > (handle_builtin_strcat): Likewise. > (handle_builtin_malloc): Likewise. > (handle_pointer_plus): Likewise. > (handle_builtin_memcpy): Likewise. Track nonzero characters > that aren't necessarily followed by a nul terminator. > (handle_char_store): Likewise. > > gcc/testsuite/ > * gcc.dg/strlenopt-32.c: New testcase. > * gcc.dg/strlenopt-33.c: Likewise. > * gcc.dg/strlenopt-33g.c: Likewise. > * gcc.dg/strlenopt-34.c: Likewise. > * gcc.dg/strlenopt-35.c: Likewise. Ok, with a small nit. > @@ -501,8 +550,8 @@ set_endptr_and_length (location_t loc, s > static tree > get_string_length (strinfo *si) > { > - if (si->length) > - return si->length; > + if (si->nonzero_chars) > + return si->full_string_p ? si->nonzero_chars : NULL; This should be NULL_TREE. > > if (si->stmt) > { > @@ -595,19 +644,19 @@ get_string_length (strinfo *si) > for (strinfo *chainsi = verify_related_strinfos (si); > chainsi != NULL; > chainsi = get_next_strinfo (chainsi)) > - if (chainsi->length == NULL) > + if (chainsi->nonzero_chars == NULL) and this actually too (though it is preexisting). For future work, it would be nice if we could handle not just memcpy and single character stores, but also cases where a memcpy is folded into a store of couple of adjacent bytes, say MEM_REF[ptr, 0] = 0x12345678; is storing 4 non-zero bytes, while = 0x345678; would be zero nonzero_chars + full_string_p for big endian and 3 non-zero bytes plus zero byte on little endian. One could use native_encode_expr on the rhs and then determine the nonzero count at the start and optional presence of a zero char afterwards. Jakub
Index: gcc/tree-ssa-strlen.c =================================================================== --- gcc/tree-ssa-strlen.c 2017-02-23 19:54:03.000000000 +0000 +++ gcc/tree-ssa-strlen.c 2017-05-05 12:53:08.764475923 +0100 @@ -99,6 +99,9 @@ struct strinfo /* A flag for the next maybe_invalidate that this strinfo shouldn't be invalidated. Always cleared by maybe_invalidate. */ bool dont_invalidate; + /* True if the string is nul-terminated. False is useful when + detecting strings that are built up via successive memcpys. */ + bool terminated; }; /* Pool for allocating strinfo_struct entries. */ @@ -400,7 +403,7 @@ new_addr_stridx (tree exp) /* Create a new strinfo. */ static strinfo * -new_strinfo (tree ptr, int idx, tree length) +new_strinfo (tree ptr, int idx, tree length, bool terminated) { strinfo *si = strinfo_pool.allocate (); si->length = length; @@ -414,6 +417,7 @@ new_strinfo (tree ptr, int idx, tree len si->next = 0; si->writable = false; si->dont_invalidate = false; + si->terminated = terminated; return si; } @@ -443,6 +447,9 @@ set_strinfo (int idx, strinfo *si) static tree get_string_length (strinfo *si) { + if (!si->terminated) + return NULL; + if (si->length) return si->length; @@ -595,7 +602,7 @@ unshare_strinfo (strinfo *si) if (si->refcount == 1 && !strinfo_shared ()) return si; - nsi = new_strinfo (si->ptr, si->idx, si->length); + nsi = new_strinfo (si->ptr, si->idx, si->length, si->terminated); nsi->stmt = si->stmt; nsi->endptr = si->endptr; nsi->first = si->first; @@ -694,7 +701,8 @@ get_stridx_plus_constant (strinfo *bases int idx = new_stridx (ptr); if (idx == 0) return 0; - si = new_strinfo (ptr, idx, build_int_cst (size_type_node, len)); + si = new_strinfo (ptr, idx, build_int_cst (size_type_node, len), + basesi->terminated); set_strinfo (idx, si); if (chainsi->next) { @@ -778,7 +786,7 @@ zero_length_string (tree ptr, strinfo *c idx = new_stridx (ptr); if (idx == 0) return NULL; - si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0)); + si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0), true); set_strinfo (idx, si); si->endptr = ptr; if (chainsi != NULL) @@ -797,11 +805,12 @@ zero_length_string (tree ptr, strinfo *c } /* For strinfo ORIGSI whose length has been just updated - update also related strinfo lengths (add ADJ to each, - but don't adjust ORIGSI). */ + update also related strinfo lengths (add ADJ to each, and change + the terminated flag to TERMINATED, but don't adjust ORIGSI). */ static void -adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj) +adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj, + bool terminated) { strinfo *si = verify_related_strinfos (origsi); @@ -823,10 +832,11 @@ adjust_related_strinfos (location_t loc, si->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (si->length), si->length, tem); + si->terminated = terminated; } else if (si->stmt != NULL) /* Delayed length computation is unaffected. */ - ; + si->terminated = terminated; else gcc_unreachable (); @@ -1009,7 +1019,9 @@ adjust_last_stmt (strinfo *si, gimple *s if (!is_strcat) { - if (si->length == NULL_TREE || !integer_zerop (si->length)) + if (si->length == NULL_TREE + || !integer_zerop (si->length) + || !si->terminated) return; } @@ -1131,6 +1143,7 @@ handle_builtin_strlen (gimple_stmt_itera { si = unshare_strinfo (si); si->length = lhs; + gcc_assert (si->terminated); } return; } @@ -1143,7 +1156,7 @@ handle_builtin_strlen (gimple_stmt_itera return; if (idx) { - strinfo *si = new_strinfo (src, idx, lhs); + strinfo *si = new_strinfo (src, idx, lhs, true); set_strinfo (idx, si); find_equal_ptrs (src, idx); } @@ -1247,7 +1260,7 @@ handle_builtin_strchr (gimple_stmt_itera tree srcu = fold_convert_loc (loc, size_type_node, src); tree length = fold_build2_loc (loc, MINUS_EXPR, size_type_node, lhsu, srcu); - strinfo *si = new_strinfo (src, idx, length); + strinfo *si = new_strinfo (src, idx, length, true); si->endptr = lhs; set_strinfo (idx, si); find_equal_ptrs (src, idx); @@ -1339,6 +1352,7 @@ handle_builtin_strcpy (enum built_in_fun oldlen = olddsi->length; dsi = unshare_strinfo (olddsi); dsi->length = srclen; + dsi->terminated = true; /* Break the chain, so adjust_related_strinfo on later pointers in the chain won't adjust this one anymore. */ dsi->next = 0; @@ -1347,7 +1361,7 @@ handle_builtin_strcpy (enum built_in_fun } else { - dsi = new_strinfo (dst, didx, srclen); + dsi = new_strinfo (dst, didx, srclen, true); set_strinfo (didx, dsi); find_equal_ptrs (dst, didx); } @@ -1376,6 +1390,7 @@ handle_builtin_strcpy (enum built_in_fun chainsi = unshare_strinfo (chainsi); chainsi->stmt = stmt; chainsi->length = NULL_TREE; + chainsi->terminated = true; chainsi->endptr = NULL_TREE; chainsi->dont_invalidate = true; } @@ -1398,7 +1413,7 @@ handle_builtin_strcpy (enum built_in_fun fold_convert_loc (loc, TREE_TYPE (srclen), oldlen)); if (adj != NULL_TREE) - adjust_related_strinfos (loc, dsi, adj); + adjust_related_strinfos (loc, dsi, adj, true); else dsi->prev = 0; } @@ -1543,31 +1558,45 @@ handle_builtin_memcpy (enum built_in_fun && !integer_zerop (len)) adjust_last_stmt (olddsi, stmt, false); + bool terminated; if (idx > 0) { gimple *def_stmt; - /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */ + /* Handle memcpy (x, y, l) where l is strlen (y){, + 1}. */ si = get_strinfo (idx); if (si == NULL || si->length == NULL_TREE) return; - if (TREE_CODE (len) != SSA_NAME) - return; - def_stmt = SSA_NAME_DEF_STMT (len); - if (!is_gimple_assign (def_stmt) - || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR - || gimple_assign_rhs1 (def_stmt) != si->length - || !integer_onep (gimple_assign_rhs2 (def_stmt))) - return; + if (len == si->length) + terminated = false; + else + { + if (!si->terminated) + return; + if (TREE_CODE (len) != SSA_NAME) + return; + def_stmt = SSA_NAME_DEF_STMT (len); + if (!is_gimple_assign (def_stmt) + || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR + || gimple_assign_rhs1 (def_stmt) != si->length + || !integer_onep (gimple_assign_rhs2 (def_stmt))) + return; + terminated = true; + } } else { si = NULL; /* Handle memcpy (x, "abcd", 5) or memcpy (x, "abc\0uvw", 7). */ - if (!tree_fits_uhwi_p (len) - || tree_to_uhwi (len) <= (unsigned HOST_WIDE_INT) ~idx) + if (!tree_fits_uhwi_p (len)) + return; + + unsigned HOST_WIDE_INT clen = tree_to_uhwi (len); + if (clen < (unsigned HOST_WIDE_INT) ~idx) return; + + terminated = (clen > (unsigned HOST_WIDE_INT) ~idx); } if (olddsi != NULL && TREE_CODE (len) == SSA_NAME) @@ -1589,6 +1618,7 @@ handle_builtin_memcpy (enum built_in_fun dsi = unshare_strinfo (olddsi); oldlen = olddsi->length; dsi->length = newlen; + dsi->terminated = terminated; /* Break the chain, so adjust_related_strinfo on later pointers in the chain won't adjust this one anymore. */ dsi->next = 0; @@ -1597,7 +1627,7 @@ handle_builtin_memcpy (enum built_in_fun } else { - dsi = new_strinfo (dst, didx, newlen); + dsi = new_strinfo (dst, didx, newlen, terminated); set_strinfo (didx, dsi); find_equal_ptrs (dst, didx); } @@ -1618,7 +1648,7 @@ handle_builtin_memcpy (enum built_in_fun fold_convert_loc (loc, TREE_TYPE (dsi->length), oldlen)); if (adj != NULL_TREE) - adjust_related_strinfos (loc, dsi, adj); + adjust_related_strinfos (loc, dsi, adj, terminated); else dsi->prev = 0; } @@ -1627,27 +1657,30 @@ handle_builtin_memcpy (enum built_in_fun if (si != NULL) si->dont_invalidate = true; - lhs = gimple_call_lhs (stmt); - switch (bcode) + if (terminated) { - case BUILT_IN_MEMCPY: - case BUILT_IN_MEMCPY_CHK: - case BUILT_IN_MEMCPY_CHKP: - case BUILT_IN_MEMCPY_CHK_CHKP: - /* Allow adjust_last_stmt to decrease this memcpy's size. */ - laststmt.stmt = stmt; - laststmt.len = dsi->length; - laststmt.stridx = dsi->idx; - if (lhs) - ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; - break; - case BUILT_IN_MEMPCPY: - case BUILT_IN_MEMPCPY_CHK: - case BUILT_IN_MEMPCPY_CHKP: - case BUILT_IN_MEMPCPY_CHK_CHKP: - break; - default: - gcc_unreachable (); + lhs = gimple_call_lhs (stmt); + switch (bcode) + { + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMCPY_CHK: + case BUILT_IN_MEMCPY_CHKP: + case BUILT_IN_MEMCPY_CHK_CHKP: + /* Allow adjust_last_stmt to decrease this memcpy's size. */ + laststmt.stmt = stmt; + laststmt.len = dsi->length; + laststmt.stridx = dsi->idx; + if (lhs) + ssa_ver_to_stridx[SSA_NAME_VERSION (lhs)] = didx; + break; + case BUILT_IN_MEMPCPY: + case BUILT_IN_MEMPCPY_CHK: + case BUILT_IN_MEMPCPY_CHKP: + case BUILT_IN_MEMPCPY_CHK_CHKP: + break; + default: + gcc_unreachable (); + } } } @@ -1696,7 +1729,7 @@ handle_builtin_strcat (enum built_in_fun } if (dsi == NULL) { - dsi = new_strinfo (dst, didx, NULL_TREE); + dsi = new_strinfo (dst, didx, NULL_TREE, true); set_strinfo (didx, dsi); find_equal_ptrs (dst, didx); } @@ -1704,6 +1737,7 @@ handle_builtin_strcat (enum built_in_fun { dsi = unshare_strinfo (dsi); dsi->length = NULL_TREE; + dsi->terminated = true; dsi->next = 0; dsi->endptr = NULL_TREE; } @@ -1739,7 +1773,7 @@ handle_builtin_strcat (enum built_in_fun { dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length), dsi->length, srclen); - adjust_related_strinfos (loc, dsi, srclen); + adjust_related_strinfos (loc, dsi, srclen, true); dsi->dont_invalidate = true; } else @@ -1877,7 +1911,7 @@ handle_builtin_malloc (enum built_in_fun tree length = NULL_TREE; if (bcode == BUILT_IN_CALLOC) length = build_int_cst (size_type_node, 0); - strinfo *si = new_strinfo (lhs, idx, length); + strinfo *si = new_strinfo (lhs, idx, length, bcode == BUILT_IN_CALLOC); if (bcode == BUILT_IN_CALLOC) si->endptr = lhs; set_strinfo (idx, si); @@ -1920,6 +1954,7 @@ handle_builtin_memset (gimple_stmt_itera update_gimple_call (&gsi1, builtin_decl_implicit (BUILT_IN_CALLOC), 2, size, build_one_cst (size_type_node)); si1->length = build_int_cst (size_type_node, 0); + si1->terminated = true; si1->stmt = gsi_stmt (gsi1); } else @@ -2056,12 +2091,13 @@ handle_pointer_plus (gimple_stmt_iterato off = gimple_assign_rhs2 (stmt); zsi = NULL; - if (operand_equal_p (si->length, off, 0)) + if (si->terminated && operand_equal_p (si->length, off, 0)) zsi = zero_length_string (lhs, si); else if (TREE_CODE (off) == SSA_NAME) { gimple *def_stmt = SSA_NAME_DEF_STMT (off); if (gimple_assign_single_p (def_stmt) + && si->terminated && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0)) zsi = zero_length_string (lhs, si); } @@ -2088,6 +2124,8 @@ handle_char_store (gimple_stmt_iterator strinfo *si = NULL; gimple *stmt = gsi_stmt (*gsi); tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt); + tree rhs = gimple_assign_rhs1 (stmt); + int terminated = -1; if (TREE_CODE (lhs) == MEM_REF && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME) @@ -2101,12 +2139,18 @@ handle_char_store (gimple_stmt_iterator else idx = get_addr_stridx (lhs, NULL_TREE); + if (initializer_zerop (rhs)) + terminated = 1; + else if (TREE_CODE (rhs) == INTEGER_CST && integer_nonzerop (rhs)) + terminated = 0; + if (idx > 0) { si = get_strinfo (idx); if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length)) { - if (initializer_zerop (gimple_assign_rhs1 (stmt))) + /* We're writing to the end of a previous string. */ + if (si->terminated && terminated == 1) { /* When storing '\0', the store can be removed if we know it has been stored in the current function. */ @@ -2125,15 +2169,20 @@ handle_char_store (gimple_stmt_iterator } } else - /* Otherwise this statement overwrites the '\0' with - something, if the previous stmt was a memcpy, - its length may be decreased. */ - adjust_last_stmt (si, stmt, false); + { + /* Otherwise leave the entry alone and allow it to be + invalidated. */ + if (si->terminated) + /* This statement overwrites the '\0' with something, if the + previous stmt was a memcpy, its length may be decreased. */ + adjust_last_stmt (si, stmt, false); + } } - else if (si != NULL && integer_zerop (gimple_assign_rhs1 (stmt))) + else if (si != NULL && terminated == 1) { si = unshare_strinfo (si); si->length = build_int_cst (size_type_node, 0); + si->terminated = true; si->endptr = NULL; si->prev = 0; si->next = 0; @@ -2164,35 +2213,31 @@ handle_char_store (gimple_stmt_iterator bar (len, len2, len3, len4); } */ - else if (si != NULL && si->length != NULL_TREE + else if (si != NULL + && si->length != NULL_TREE && TREE_CODE (si->length) == INTEGER_CST - && integer_nonzerop (gimple_assign_rhs1 (stmt))) + && terminated == 0) { gsi_next (gsi); return false; } } - else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt))) + else if (idx == 0 && terminated >= 0) { if (ssaname) - { - si = zero_length_string (ssaname, NULL); - if (si != NULL) - si->dont_invalidate = true; - } + idx = new_stridx (ssaname); else + idx = new_addr_stridx (lhs); + if (idx != 0) { - int idx = new_addr_stridx (lhs); - if (idx != 0) - { - si = new_strinfo (build_fold_addr_expr (lhs), idx, - build_int_cst (size_type_node, 0)); - set_strinfo (idx, si); - si->dont_invalidate = true; - } + tree ptr = (ssaname ? ssaname : build_fold_addr_expr (lhs)); + si = new_strinfo (ptr, idx, size_int (!terminated), terminated); + set_strinfo (idx, si); + if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) + si->endptr = ssaname; + si->dont_invalidate = true; + si->writable = true; } - if (si != NULL) - si->writable = true; } else if (idx == 0 && TREE_CODE (gimple_assign_rhs1 (stmt)) == STRING_CST @@ -2207,14 +2252,14 @@ handle_char_store (gimple_stmt_iterator if (idx != 0) { si = new_strinfo (build_fold_addr_expr (lhs), idx, - build_int_cst (size_type_node, l)); + build_int_cst (size_type_node, l), true); set_strinfo (idx, si); si->dont_invalidate = true; } } } - if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt))) + if (si != NULL && terminated == 1) { /* Allow adjust_last_stmt to remove it if the stored '\0' is immediately overwritten. */ Index: gcc/testsuite/gcc.dg/strlenopt-31.c =================================================================== --- /dev/null 2017-05-05 07:30:08.141451281 +0100 +++ gcc/testsuite/gcc.dg/strlenopt-31.c 2017-05-05 12:53:08.763475920 +0100 @@ -0,0 +1,57 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +volatile int v; + +size_t +f1 (void) +{ + char a[30]; + v += 1; + memcpy (a, "1234567", 7); + memcpy (a + 7, "89abcdefg", 9); + memcpy (a + 16, "h", 2); + return strlen (a); // This strlen should be optimized into 17. +} + +size_t +f2 (char *a) +{ + v += 2; + memcpy (a, "1234567", 7); + memcpy (a + 7, "89abcdefg", 9); + memcpy (a + 16, "h", 2); + return strlen (a); // This strlen should be optimized into 17. +} + +size_t +f3 (void) +{ + char a[30]; + v += 3; + a[0] = '1'; + memcpy (a + 1, "2345678", 8); + return strlen (a); // This strlen should be optimized into 8. +} + +size_t +f4 (char *a) +{ + v += 4; + a[0] = '1'; + memcpy (a + 1, "2345678", 8); + return strlen (a); // This strlen should be optimized into 8. +} + +int +main () +{ + char a[30]; + if (f1 () != 17 || f2 (a) != 17 || f3 () != 8 || f4 (a) != 8) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */
tree-ssa-strlen.c looks for cases in which a string is built up using operations like: memcpy (a, "foo", 4); memcpy (a + 3, "bar", 4); int x = strlen (a); As a side-effect, it optimises the non-final memcpys so that they don't include the nul terminator. However, after removing some "& ~0x1"s from tree-ssa-dse.c, the DSE pass does this optimisation itself (because it can tell that later memcpys overwrite the terminators). The strlen pass wasn't able to handle these pre-optimised calls in the same way as the unoptimised ones. This patch adds support for tracking unterminated strings. Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? Thanks, Richard [Based on commit branches/ARM/sve-branch@246236] 2017-05-05 Richard Sandiford <richard.sandiford@linaro.org> gcc/ * tree-ssa-strlen.c (strinfo): Add a terminated field. (new_strinfo): Add a corresponding parameter and initialize the field. (get_string_length): Return null for unterminated strings. (unshare_strinfo): Update call to new_strinfo. (get_stridx_plus_constant): Likewise. (zero_length_string): Likewise. (handle_builtin_strchr): Likewise. (handle_builtin_strcat): Likewise. (handle_builtin_malloc): Likewise. (adjust_related_strinfos): Add a terminated parameter. (adjust_last_stmt): Update test for a zero-length terminated string. (handle_builtin_strlen): Assert that we can only know the length of terminated strings. Update calls to new_strinfo. (handle_builtin_strcpy): Update calls to new_strinfo and set the terminated field when adjusting strinfos manually. (handle_builtin_memcpy): Handle unterminated strings. Update calls to new_strinfo. (handle_builtin_memset): Initialize the terminated field. (handle_pointer_plus): Check for terminated strings. (handle_char_store): Handle unterminated strings. gcc/testsuite/ * gcc.dg/strlenopt-31.c: New testcase.