Bug 83642 - excessive strlen range after a strcat of non-empty string
Summary: excessive strlen range after a strcat of non-empty string
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 8.0
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
Depends on:
Blocks: strlen
  Show dependency treegraph
 
Reported: 2017-12-31 21:34 UTC by Martin Sebor
Modified: 2019-10-15 22:41 UTC (History)
0 users

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2018-01-01 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Martin Sebor 2017-12-31 21:34:02 UTC
The test case below (derived from bug 83640, comment #4) highlights a possible optimization opportunity in the strlen pass.  So that the difference between pointers to the first and just past the last byte of any array must be at most PTRDIFF_MAX bytes the size of the largest array is PTRDIFF_MAX bytes.  Since the length of the string literal appended to the DST array by the first strcat call below is known to be 2, then length of the DST string must be less than PTRDIFF_MAX - 2.  Therefore the test can be assumed to never evaluate to true and the call to abort can be eliminated.

$ cat a.c && gcc -O2 -S -fdump-tree-vrp=/dev/stdout a.c
char *foo (void);

void
bar (char *dst, char *src)
{
  __SIZE_TYPE__ n = __builtin_strlen (dst);

  __builtin_strcat (dst, "*/");   // implies n < PTRDIFF_MAX - 3
  __builtin_strcat (dst, src);

  if (n >= __PTRDIFF_MAX__ - 2)   // must be false
    __builtin_abort ();           // can be eliminated
}

...
Value ranges after VRP:

dst_2(D): VARYING
n_3: [0, 9223372036854775806]
_4: VARYING
_9: [2, 9223372036854775808]
_10: VARYING
dst_11: ~[0B, 0B]  EQUIVALENCES: { dst_2(D) } (1 elements)


bar (char * dst, char * src)
{
  long unsigned int n;
  char * _4;
  long unsigned int _9;
  char * _10;

  <bb 2> [local count: 1073741825]:
  n_3 = __builtin_strlen (dst_2(D));
  _4 = dst_2(D) + n_3;
  __builtin_memcpy (_4, "*/", 2);
  _9 = n_3 + 2;
  _10 = dst_2(D) + _9;
  __builtin_strcpy (_10, src_6(D));
  if (n_3 > 9223372036854775804)
    goto <bb 3>; [0.00%]
  else
    goto <bb 4>; [99.96%]

  <bb 3> [count: 0]:
  __builtin_abort ();

  <bb 4> [local count: 1073312327]:
  return;

}
Comment 1 Martin Sebor 2018-01-01 22:34:22 UTC
Patch: https://gcc.gnu.org/ml/gcc-patches/2018-01/msg00003.html
Comment 2 Martin Sebor 2019-10-15 22:41:25 UTC
The patch was incorrect and I'm not actively working on a solution.