[PATCH] add --param ssa-name-def-chain-limit

[PATCH] add --param ssa-name-def-chain-limit

[Martin Sebor]

[-- Attachment #1: Type: text/plain, Size: 742 bytes --]

Attached is a patch that adds a new parameter to limit the number
of SSA_NAME assignments for GCC to follow in iterative or recursive
algorithms.  Purely as a proof of concept the patch introduces
the parameter into -Warray-bounds where the warning follows
POINTER_PLUS (and ASSERT_EXPR) assignments to get at the DECL
the final pointer points to.

With this "infrastructure" in place the parameter can start to be
introduced wherever else it might be necessary.  I don't know of
any pathological cases where it actually is necessary (i.e., one
the 512 default keeps from going off the rails) so the test I have
put together for it is artificial.  A better test case involving
one of the known recursive algorithms would be helpful.

Martin


[-- Attachment #2: gcc-param-ssa-name-def-chain-limit.diff --]
[-- Type: text/x-patch, Size: 5028 bytes --]

gcc/ChangeLog:

	* doc/invoke.texi (ssa-name-def-chain-limit): Document new --param.
	* params.def (PARAM_SSA_NAME_DEF_CHAIN_LIMIT): Add new --param.
	* tree-vrp.c (vrp_prop::check_mem_ref): Use
	PARAM_SSA_NAME_DEF_CHAIN_LIMIT.

gcc/testsuite/ChangeLog:

	* gcc.dg/Warray-bounds-43.c: New test.

Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 273357)
+++ gcc/doc/invoke.texi	(working copy)
@@ -12225,6 +12225,13 @@ before the loop versioning pass considers it too b
 discounting any instructions in inner loops that directly benefit
 from versioning.
 
+@item ssa-name-def-chain-limit
+The maximum number of SSA_NAME assignments to follow in determining
+a property of a variable such as its value.  This limits the number
+of iterations or recursive calls GCC performs when optimizing certain
+statements or when determining their validity prior to issuing
+diagnostics.
+
 @end table
 @end table
 
Index: gcc/params.def
===================================================================
--- gcc/params.def	(revision 273357)
+++ gcc/params.def	(working copy)
@@ -1437,6 +1437,12 @@ DEFPARAM(PARAM_HASH_TABLE_VERIFICATION_LIMIT,
 	 "each searched element.",
 	 10, 0, 0)
 
+DEFPARAM(PARAM_SSA_NAME_DEF_CHAIN_LIMIT,
+	 "ssa-name-def-chain-limit",
+	 "The maximum number of SSA_NAME assignments to follow in determining "
+	 "a value.",
+	 512, 0, 0)
+
 /*
 
 Local variables:
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 273357)
+++ gcc/tree-vrp.c	(working copy)
@@ -4492,7 +4492,8 @@ vrp_prop::check_mem_ref (location_t location, tree
      The loop computes the range of the final offset for expressions such
      as (A + i0 + ... + iN)[CSTOFF] where i0 through iN are SSA_NAMEs in
      some range.  */
-  while (TREE_CODE (arg) == SSA_NAME)
+  const unsigned limit = PARAM_VALUE (PARAM_SSA_NAME_DEF_CHAIN_LIMIT);
+  for (unsigned n = 0; TREE_CODE (arg) == SSA_NAME && n < limit; ++n)
     {
       gimple *def = SSA_NAME_DEF_STMT (arg);
       if (!is_gimple_assign (def))
Index: gcc/testsuite/gcc.dg/Warray-bounds-43.c
===================================================================
--- gcc/testsuite/gcc.dg/Warray-bounds-43.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/Warray-bounds-43.c	(working copy)
@@ -0,0 +1,133 @@
+/* Test to verify that --param ssa_name_def_chain_limit can be used to
+   limit the maximum number of SSA_NAME assignments the warning follows.
+   { dg-do compile }
+   { dg-options "-O2 -Wall --param ssa-name-def-chain-limit=4" }  */
+
+#define NOIPA __attribute__ ((noipa))
+
+const char a0[] = "";
+const char a1[] = "1";
+const char a2[] = "12";
+const char a3[] = "123";
+const char a4[] = "1234";
+const char a5[] = "12345";
+const char a6[] = "123456";
+const char a7[] = "1234567";
+const char a8[] = "12345678";
+const char a9[] = "123456789";
+
+void f (const char*, ...);
+
+int i0, i1, i2, i3, i4, i5, i6, i7, i8;
+
+NOIPA int g2 (int i)
+{
+  if (i < 1) i = 1;
+
+  const char *p0 = a9;
+  const char *p1 = p0 + i;
+  const char *p2 = p1 + i;
+
+  f (p0, p1, p2);
+
+  return p2[8];     // { dg-warning "\\\[-Warray-bounds]" }
+}
+
+NOIPA int g3 (int i)
+{
+  if (i < 1) i = 1;
+
+  const char *p0 = a9;
+  const char *p1 = p0 + i;
+  const char *p2 = p1 + i;
+  const char *p3 = p2 + i;
+
+  f (p0, p1, p2, p3);
+
+  return p3[7];     // { dg-warning "\\\[-Warray-bounds]" }
+}
+
+NOIPA int g4 (int i)
+{
+  if (i < 1) i = 1;
+
+  const char *p0 = a9;
+  const char *p1 = p0 + i;
+  const char *p2 = p1 + i;
+  const char *p3 = p2 + i;
+  const char *p4 = p3 + i;
+
+  f (p0, p1, p2, p3, p4);
+
+  return p4[6];     // { dg-warning "\\\[-Warray-bounds]" }
+}
+
+NOIPA int g5 (int i)
+{
+  if (i < 1) i = 1;
+
+  const char *p0 = a9;
+  const char *p1 = p0 + i;
+  const char *p2 = p1 + i;
+  const char *p3 = p2 + i;
+  const char *p4 = p3 + i;
+  const char *p5 = p4 + i;
+
+  f (p0, p1, p2, p3, p4, p5);
+
+  return p5[5];
+}
+
+NOIPA int g6 (int i)
+{
+  if (i < 1) i = 1;
+
+  const char *p0 = a9;
+  const char *p1 = p0 + i;
+  const char *p2 = p1 + i;
+  const char *p3 = p2 + i;
+  const char *p4 = p3 + i;
+  const char *p5 = p4 + i;
+  const char *p6 = p5 + i;
+
+  f (p0, p1, p2, p3, p4, p5, p6);
+
+  return p6[4];
+}
+
+NOIPA int g7 (int i)
+{
+  if (i < 1) i = 1;
+
+  const char *p0 = a9;
+  const char *p1 = p0 + i;
+  const char *p2 = p1 + i;
+  const char *p3 = p2 + i;
+  const char *p4 = p3 + i;
+  const char *p5 = p4 + i;
+  const char *p6 = p5 + i;
+  const char *p7 = p6 + i;
+
+  f (p0, p1, p2, p3, p4, p5, p6, p7);
+
+  return p7[3];
+}
+
+NOIPA int g8 (int i)
+{
+  if (i < 1) i = 1;
+
+  const char *p0 = a9;
+  const char *p1 = p0 + i;
+  const char *p2 = p1 + i;
+  const char *p3 = p2 + i;
+  const char *p4 = p3 + i;
+  const char *p5 = p4 + i;
+  const char *p6 = p5 + i;
+  const char *p7 = p6 + i;
+  const char *p8 = p7 + i;
+
+  f (p0, p1, p2, p3, p4, p5, p6, p7, p8);
+
+  return p8[2];
+}

Re: [PATCH] add --param ssa-name-def-chain-limit

[Richard Biener]

On Thu, Jul 11, 2019 at 7:43 PM Martin Sebor <msebor@gmail.com> wrote:
>
> Attached is a patch that adds a new parameter to limit the number
> of SSA_NAME assignments for GCC to follow in iterative or recursive
> algorithms.  Purely as a proof of concept the patch introduces
> the parameter into -Warray-bounds where the warning follows
> POINTER_PLUS (and ASSERT_EXPR) assignments to get at the DECL
> the final pointer points to.
>
> With this "infrastructure" in place the parameter can start to be
> introduced wherever else it might be necessary.  I don't know of
> any pathological cases where it actually is necessary (i.e., one
> the 512 default keeps from going off the rails) so the test I have
> put together for it is artificial.  A better test case involving
> one of the known recursive algorithms would be helpful.

The docs talk about diagnostics so I wonder if the param
name should include that as well, otherwise OK.

Thanks,
Richard.

> Martin
>

Re: [PATCH] add --param ssa-name-def-chain-limit

[Martin Sebor]

On 7/12/19 3:35 AM, Richard Biener wrote:
> On Thu, Jul 11, 2019 at 7:43 PM Martin Sebor <msebor@gmail.com> wrote:
>>
>> Attached is a patch that adds a new parameter to limit the number
>> of SSA_NAME assignments for GCC to follow in iterative or recursive
>> algorithms.  Purely as a proof of concept the patch introduces
>> the parameter into -Warray-bounds where the warning follows
>> POINTER_PLUS (and ASSERT_EXPR) assignments to get at the DECL
>> the final pointer points to.
>>
>> With this "infrastructure" in place the parameter can start to be
>> introduced wherever else it might be necessary.  I don't know of
>> any pathological cases where it actually is necessary (i.e., one
>> the 512 default keeps from going off the rails) so the test I have
>> put together for it is artificial.  A better test case involving
>> one of the known recursive algorithms would be helpful.
> 
> The docs talk about diagnostics so I wonder if the param
> name should include that as well, otherwise OK.

I committed the patch as is for now.  The parameter's effect is
on both, optimization and diagnostics, so a generic name seems
like a good fit.  Plus, I couldn't off hand think of a better
name.  We can always change it if you or someone else comes up
with one.

Martin