PR tree-optimization/91996 - fold non-constant strlen relational expressions
gcc/testsuite/ChangeLog:
PR tree-optimization/91996
* gcc.dg/strlenopt-80.c: New test.
* gcc.dg/strlenopt-81.c: New test.
gcc/ChangeLog:
PR tree-optimization/91996
* tree-ssa-strlen.c (maybe_warn_pointless_strcmp): Improve location
information.
(compare_nonzero_chars): Add an overload.
(count_nonzero_bytes): Add an argument. Call overload above.
Handle non-constant lengths in some range.
(handle_store): Add an argument.
(check_and_optimize_stmt): Pass an argument to handle_store.
new file mode 100644
@@ -0,0 +1,95 @@
+/* PR tree-optimization/91996 - fold strlen relational expressions
+ { dg-do compile }
+ { dg-options "-O2 -Wall -fdump-tree-optimized" } */
+
+#define CHAR_BIT __CHAR_BIT__
+#define SIZE_MAX __SIZE_MAX__
+#define LEN_MAX (__PTRDIFF_MAX__ - 2)
+
+typedef __PTRDIFF_TYPE__ ptrdiff_t;
+typedef __SIZE_TYPE__ size_t;
+
+extern void* memcpy (void*, const void*, size_t);
+extern size_t strlen (const char*);
+
+#define CONCAT(a, b) a ## b
+#define CAT(a, b) CONCAT (a, b)
+
+extern void sink (void*, ...);
+extern void failure_on_line (int);
+
+extern char src[];
+extern char dst[];
+
+/* Copy (1 << NCPYLOG) bytes from an unknown string SRC with strlen (SRC)
+ in the range [MINSRCLEN, MAXSRCLEN] into DST + DSTOFF and verify that
+ strlen (DST + DSTOFF) is in the range [MINDSTLEN, MAXDSTLEN]. */
+#define MIN_MAX(dst, dstoff, src, \
+ minsrclen, maxsrclen, mindstlen, maxdstlen, ncpylog) \
+ void CAT (test_on_line_, __LINE__) (void) \
+ { \
+ size_t srclen = strlen (src); \
+ if ((minsrclen) <= srclen && srclen <= (maxsrclen)) { \
+ char *d = (dst) + (dstoff); \
+ memcpy (d, src, (size_t)1 << (ncpylog)); \
+ size_t dstlen = strlen (d); \
+ if (dstlen < (mindstlen) || (maxdstlen) < dstlen) \
+ { \
+ failure_on_line (__LINE__); \
+ } \
+ sink (dst, src); \
+ } \
+ } typedef void dummy_type
+
+// Verify the lower bound of the resulting strlen range.
+#define MIN(dst, dstoff, src, minsrclen, mindstlen, ncpylog) \
+ MIN_MAX (dst, dstoff, src, minsrclen, LEN_MAX, mindstlen, LEN_MAX, ncpylog)
+
+MIN (dst, 0, src, 2, 1, 0);
+MIN (dst, 0, src, 3, 1, 0);
+MIN (dst, 0, src, 3, 2, 1);
+MIN (dst, 0, src, 3, 2, 2);
+MIN (dst, 0, src, 3, 2, 3);
+
+MIN (dst, 1, src, 2, 1, 0);
+MIN (dst, 1, src, 3, 1, 0);
+MIN (dst, 1, src, 3, 2, 1);
+MIN (dst, 1, src, 3, 2, 2);
+MIN (dst, 1, src, 3, 2, 3);
+
+MIN (dst, 2, src, 2, 1, 0);
+MIN (dst, 3, src, 3, 1, 0);
+MIN (dst, 4, src, 3, 2, 1);
+MIN (dst, 5, src, 3, 2, 2);
+MIN (dst, 6, src, 3, 2, 3);
+
+
+MIN (dst, 0, src, 5, 1, 0);
+MIN (dst, 0, src, 5, 2, 1);
+MIN (dst, 0, src, 5, 4, 2);
+MIN (dst, 0, src, 5, 5, 3);
+MIN (dst, 0, src, 5, 5, 4);
+
+MIN (dst, 11, src, 5, 1, 0);
+MIN (dst, 22, src, 5, 2, 1);
+MIN (dst, 33, src, 5, 4, 2);
+MIN (dst, 44, src, 5, 5, 3);
+MIN (dst, 55, src, 5, 5, 4);
+
+MIN (dst, 11, src, LEN_MAX, 1, 0);
+MIN (dst, 22, src, LEN_MAX, 2, 1);
+MIN (dst, 33, src, LEN_MAX, 4, 2);
+MIN (dst, 44, src, LEN_MAX, 5, 3);
+MIN (dst, 55, src, LEN_MAX, 5, 4);
+MIN (dst, 66, src, LEN_MAX, 9, 8);
+MIN (dst, 66, src, LEN_MAX, LEN_MAX, sizeof (ptrdiff_t) * CHAR_BIT - 1);
+
+
+MIN_MAX (dst, 0, src, 3, 5, 1, LEN_MAX, 0);
+MIN_MAX (dst, 0, src, 3, 5, 2, LEN_MAX, 1);
+MIN_MAX (dst, 0, src, 3, 5, 3, LEN_MAX, 2);
+
+/* Upper bound not implemented yet.
+ MIN_MAX (dst, 0, src, 3, 5, 3, 5, 3); */
+
+/* { dg-final { scan-tree-dump-times "failure_on_line \\(" 0 "optimized" } } */
new file mode 100644
@@ -0,0 +1,190 @@
+/* PR tree-optimization/ - fold strlen relational expressions
+ { dg-do run }
+ { dg-options "-O2 "-Wall -fdump-tree-optimized" } */
+
+typedef __SIZE_TYPE__ size_t;
+
+#define NOIPA __attribute__ ((noipa))
+
+#define CONCAT(a, b) a ## b
+#define CAT(a, b) CONCAT (a, b)
+
+/* Used in tests where EXPR is expected to be folded to false. */
+#define ELIM(expr) \
+ if (expr) { \
+ extern void \
+ CAT (CAT (test_on_line_, __LINE__), _not_eliminated)(void); \
+ CAT (CAT (test_on_line_, __LINE__), _not_eliminated)(); \
+ } typedef void dummy_type
+
+char a[32], b[32];
+
+void init (void)
+{
+ __builtin_strncpy (a, "abcdefgh", sizeof a);
+ __builtin_strncpy (b, "0123456789", sizeof b);
+}
+
+NOIPA void fail (const char *func)
+{
+ __builtin_printf ("failure in %s\n", func);
+ __builtin_abort ();
+}
+
+NOIPA void test_global_cpy_4 (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ char *d = a;
+ __builtin_memcpy (d, b, 4);
+
+ size_t dlen = __builtin_strlen (d);
+ if (dlen != 8) // cannot be eliminated
+ fail ("test_global");
+}
+
+
+NOIPA void test_global_cpy_10 (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ char *d = a;
+ __builtin_memcpy (d, b, 10);
+
+ size_t dlen = __builtin_strlen (d);
+ if (dlen != 10) // cannot be eliminated
+ fail ("test_global_cpy_10");
+}
+
+NOIPA void test_global_cpy_11 (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ char *d = a;
+ __builtin_memcpy (d, b, 11);
+
+ size_t dlen = __builtin_strlen (d);
+ if (dlen != 10) // cannot be eliminated
+ fail ("test_global_cpy_11");
+}
+
+NOIPA void test_global_cpy_20 (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ char *d = a;
+ __builtin_memcpy (d, b, 20);
+
+ size_t dlen = __builtin_strlen (d);
+ if (dlen != 10) // cannot be eliminated
+ fail ("test_global_cpy_20");
+}
+
+NOIPA void test_local_cpy_4 (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ char a[10] = "abcdefgh";
+ char *d = a;
+ __builtin_memcpy (d, b, 4);
+
+ size_t dlen = __builtin_strlen (d);
+ ELIM (dlen != 8);
+}
+
+NOIPA void test_local_cpy_10 (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ char a[32] = "abcdefgh";
+ char *d = a;
+ __builtin_memcpy (d, b, 10);
+
+ /* B can be longer than 9 and A can initially be longer than 10
+ so the test below cannot be eliminated. */
+ size_t dlen = __builtin_strlen (d);
+ if (dlen != 10)
+ fail ("test_local_cpy_10");
+}
+
+NOIPA void test_local_cpy_11 (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ char a[32] = "abcdefgh";
+ char *d = a;
+ __builtin_memcpy (d, b, 11);
+
+ size_t dlen = __builtin_strlen (d);
+ if (dlen != 10)
+ fail ("test_global_cpy_20");
+}
+
+NOIPA void test_local_cpy_20 (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ char a[32] = "abcdefgh";
+ char *d = a;
+ __builtin_memcpy (d, b, 20);
+
+ size_t dlen = __builtin_strlen (d);
+ if (dlen != 10)
+ fail ("test_global_cpy_20");
+}
+
+NOIPA void test_global_length_eq (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen != 10) return;
+
+ size_t alen = __builtin_strlen (a);
+ if (alen != 8) return;
+
+ char *d = a;
+ __builtin_memcpy (d, b, 4);
+
+ size_t dlen = __builtin_strlen (d);
+ ELIM (dlen != 8);
+}
+
+
+NOIPA void test_global_length_gt (void)
+{
+ size_t blen = __builtin_strlen (b);
+ if (blen < 9) return;
+
+ size_t alen = __builtin_strlen (a);
+ if (alen < 8) return;
+
+ char *d = a;
+ __builtin_memcpy (d, b, 4);
+
+ size_t dlen = __builtin_strlen (d);
+ ELIM (dlen < 8);
+}
+
+#define TEST(name) do { init (); test_ ## name (); } while (0)
+
+int main (void)
+{
+ TEST (local_cpy_4);
+ TEST (local_cpy_10);
+ TEST (local_cpy_11);
+ TEST (local_cpy_20);
+
+ TEST (global_cpy_4);
+ TEST (global_cpy_10);
+ TEST (global_cpy_11);
+ TEST (global_cpy_20);
+ TEST (global_length_eq);
+ TEST (global_length_gt);
+}
@@ -191,12 +191,12 @@ static void handle_builtin_stxncpy (built_in_function, gimple_stmt_iterator *);
/* Return:
- - 1 if SI is known to start with more than OFF nonzero characters.
+ * +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.
+ * 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. */
+ * -1 if SI might not start with OFF nonzero characters. */
static inline int
compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off)
@@ -208,6 +208,33 @@ compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off)
return -1;
}
+/* Same as above but suitable also for strings with non-constant lengths.
+ Uses RVALS to determine length range. */
+
+static int
+compare_nonzero_chars (strinfo *si, unsigned HOST_WIDE_INT off,
+ const vr_values *rvals)
+{
+ if (!si->nonzero_chars)
+ return -1;
+
+ if (TREE_CODE (si->nonzero_chars) == INTEGER_CST)
+ return compare_tree_int (si->nonzero_chars, off);
+
+ if (TREE_CODE (si->nonzero_chars) != SSA_NAME)
+ return -1;
+
+ const value_range *vr
+ = (CONST_CAST (class vr_values *, rvals)
+ ->get_value_range (si->nonzero_chars));
+
+ value_range_kind rng = vr->kind ();
+ if (rng != VR_RANGE || !range_int_cst_p (vr))
+ return -1;
+
+ return compare_tree_int (vr->min (), off);
+}
+
/* Return true if SI is known to be a zero-length string. */
static inline bool
@@ -3619,7 +3646,8 @@ maybe_warn_pointless_strcmp (gimple *stmt, HOST_WIDE_INT bound,
unsigned HOST_WIDE_INT len[2],
unsigned HOST_WIDE_INT siz)
{
- gimple *use = used_only_for_zero_equality (gimple_call_lhs (stmt));
+ tree lhs = gimple_call_lhs (stmt);
+ gimple *use = used_only_for_zero_equality (lhs);
if (!use)
return;
@@ -3642,7 +3670,11 @@ maybe_warn_pointless_strcmp (gimple *stmt, HOST_WIDE_INT bound,
/* FIXME: Include a note pointing to the declaration of the smaller
array. */
- location_t stmt_loc = gimple_location (stmt);
+ location_t stmt_loc = gimple_nonartificial_location (stmt);
+ if (stmt_loc == UNKNOWN_LOCATION && EXPR_HAS_LOCATION (lhs))
+ stmt_loc = tree_nonartificial_location (lhs);
+ stmt_loc = expansion_point_location_if_in_system_header (stmt_loc);
+
tree callee = gimple_call_fndecl (stmt);
bool warned = false;
if (siz <= minlen && bound == -1)
@@ -3918,40 +3950,70 @@ static bool
count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
unsigned HOST_WIDE_INT nbytes,
unsigned lenrange[3], bool *nulterm,
- bool *allnul, bool *allnonnul, ssa_name_limit_t &snlim)
+ bool *allnul, bool *allnonnul, const vr_values *rvals,
+ ssa_name_limit_t &snlim)
{
int idx = get_stridx (exp);
if (idx > 0)
{
strinfo *si = get_strinfo (idx);
- /* FIXME: Handle non-constant lengths in some range. */
- if (!si || !tree_fits_shwi_p (si->nonzero_chars))
+ if (!si)
return false;
- unsigned len = tree_to_shwi (si->nonzero_chars);
- unsigned size = len + si->full_string_p;
- if (size <= offset)
+ /* Handle both constant lengths as well non-constant lengths
+ in some range. */
+ unsigned HOST_WIDE_INT minlen, maxlen;
+ if (tree_fits_shwi_p (si->nonzero_chars))
+ minlen = maxlen = tree_to_shwi (si->nonzero_chars);
+ else if (nbytes
+ && si->nonzero_chars
+ && TREE_CODE (si->nonzero_chars) == SSA_NAME)
+ {
+ const value_range *vr
+ = CONST_CAST (class vr_values *, rvals)
+ ->get_value_range (si->nonzero_chars);
+ if (vr->kind () != VR_RANGE
+ || !range_int_cst_p (vr))
+ return false;
+
+ minlen = tree_to_uhwi (vr->min ());
+ maxlen = tree_to_uhwi (vr->max ());
+ }
+ else
return false;
- len -= offset;
+ if (maxlen < offset)
+ return false;
- if (len < lenrange[0])
- lenrange[0] = len;
- if (lenrange[1] < len)
- lenrange[1] = len;
- if (lenrange[2] < nbytes)
- lenrange[2] = nbytes;
+ minlen = minlen < offset ? 0 : minlen - offset;
+ maxlen -= offset;
+ if (maxlen + 1 < nbytes)
+ return false;
- if (!si->full_string_p)
+ if (nbytes <= minlen)
*nulterm = false;
- /* Since only the length of the string are known and
- its contents, clear ALLNUL and ALLNONNUL purely on
- the basis of the length. */
- if (len)
- *allnul = false;
- else
+ if (nbytes < minlen)
+ {
+ minlen = nbytes;
+ if (nbytes < maxlen)
+ maxlen = nbytes;
+ }
+
+ if (minlen < lenrange[0])
+ lenrange[0] = minlen;
+ if (lenrange[1] < maxlen)
+ lenrange[1] = maxlen;
+
+ if (lenrange[2] < nbytes)
+ (lenrange[2] = nbytes);
+
+ /* Since only the length of the string are known and not its contents,
+ clear ALLNUL and ALLNONNUL purely on the basis of the length. */
+ *allnul = false;
+ if (minlen < nbytes)
*allnonnul = false;
+
return true;
}
@@ -3960,7 +4022,7 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
if (TREE_CODE (exp) == SSA_NAME)
{
- /* Handle a single-character specially. */
+ /* Handle non-zero single-character stores specially. */
tree type = TREE_TYPE (exp);
if (TREE_CODE (type) == INTEGER_TYPE
&& TYPE_MODE (type) == TYPE_MODE (char_type_node)
@@ -3972,7 +4034,7 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
for an arbitrary constant. */
exp = build_int_cst (type, 1);
return count_nonzero_bytes (exp, offset, 1, lenrange,
- nulterm, allnul, allnonnul, snlim);
+ nulterm, allnul, allnonnul, rvals, snlim);
}
gimple *stmt = SSA_NAME_DEF_STMT (exp);
@@ -3981,6 +4043,7 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
exp = gimple_assign_rhs1 (stmt);
if (TREE_CODE (exp) != MEM_REF)
return false;
+ /* Handle MEM_REF below. */
}
else if (gimple_code (stmt) == GIMPLE_PHI)
{
@@ -3996,7 +4059,7 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
{
tree def = gimple_phi_arg_def (stmt, i);
if (!count_nonzero_bytes (def, offset, nbytes, lenrange, nulterm,
- allnul, allnonnul, snlim))
+ allnul, allnonnul, rvals, snlim))
return false;
}
@@ -4033,7 +4096,7 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
/* Handle MEM_REF = SSA_NAME types of assignments. */
return count_nonzero_bytes (arg, offset, nbytes, lenrange, nulterm,
- allnul, allnonnul, snlim);
+ allnul, allnonnul, rvals, snlim);
}
if (TREE_CODE (exp) == VAR_DECL && TREE_READONLY (exp))
@@ -4132,11 +4195,13 @@ count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
return true;
}
-/* Same as above except with an implicit SSA_NAME limit. */
+/* Same as above except with an implicit SSA_NAME limit. RVALS is used
+ to determine ranges of dynamically computed string lengths (the results
+ of strlen). */
static bool
count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm,
- bool *allnul, bool *allnonnul)
+ bool *allnul, bool *allnonnul, const vr_values *rvals)
{
/* Set to optimistic values so the caller doesn't have to worry about
initializing these and to what. On success, the function will clear
@@ -4149,7 +4214,7 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm,
ssa_name_limit_t snlim;
return count_nonzero_bytes (exp, 0, 0, lenrange, nulterm, allnul, allnonnul,
- snlim);
+ rvals, snlim);
}
/* Handle a single or multibyte store other than by a built-in function,
@@ -4158,7 +4223,7 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm,
'*(int*)a = 12345'). Return true when handled. */
static bool
-handle_store (gimple_stmt_iterator *gsi)
+handle_store (gimple_stmt_iterator *gsi, const vr_values *rvals)
{
int idx = -1;
strinfo *si = NULL;
@@ -4184,7 +4249,7 @@ handle_store (gimple_stmt_iterator *gsi)
si = get_strinfo (idx);
if (offset == 0)
ssaname = TREE_OPERAND (lhs, 0);
- else if (si == NULL || compare_nonzero_chars (si, offset) < 0)
+ else if (si == NULL || compare_nonzero_chars (si, offset, rvals) < 0)
return true;
}
}
@@ -4214,7 +4279,8 @@ handle_store (gimple_stmt_iterator *gsi)
const bool ranges_valid
= count_nonzero_bytes (rhs, lenrange, &full_string_p,
- &storing_all_zeros_p, &storing_all_nonzero_p);
+ &storing_all_zeros_p, &storing_all_nonzero_p,
+ rvals);
if (ranges_valid)
{
rhs_minlen = lenrange[0];
@@ -4233,7 +4299,7 @@ handle_store (gimple_stmt_iterator *gsi)
/* Fall back on the LHS location if the statement
doesn't have one. */
location_t loc = gimple_nonartificial_location (stmt);
- if (loc == UNKNOWN_LOCATION)
+ if (loc == UNKNOWN_LOCATION && EXPR_HAS_LOCATION (lhs))
loc = tree_nonartificial_location (lhs);
loc = expansion_point_location_if_in_system_header (loc);
if (warning_n (loc, OPT_Wstringop_overflow_,
@@ -4271,15 +4337,15 @@ handle_store (gimple_stmt_iterator *gsi)
{
/* The offset of the last stored byte. */
unsigned HOST_WIDE_INT endoff = offset + lenrange[2] - 1;
- store_before_nul[0] = compare_nonzero_chars (si, offset);
+ store_before_nul[0] = compare_nonzero_chars (si, offset, rvals);
if (endoff == offset)
store_before_nul[1] = store_before_nul[0];
else
- store_before_nul[1] = compare_nonzero_chars (si, endoff);
+ store_before_nul[1] = compare_nonzero_chars (si, endoff, rvals);
}
else
{
- store_before_nul[0] = compare_nonzero_chars (si, offset);
+ store_before_nul[0] = compare_nonzero_chars (si, offset, rvals);
store_before_nul[1] = store_before_nul[0];
gcc_assert (offset == 0 || store_before_nul[0] >= 0);
}
@@ -4841,7 +4907,7 @@ check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh,
}
/* Handle a single or multibyte assignment. */
- if (is_char_store && !handle_store (gsi))
+ if (is_char_store && !handle_store (gsi, rvals))
return false;
}
}