[C++ PATCH] Add -fconstexpr-loop-nest-limit= option (PR c++/87481)

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

We have -fconstexpr-loop-limit= option to have an upper bound for constexpr
evaluation of a single loop.  Even with that limit in place, if we have
several nested loops during constexpr evaluation, even when each could have
a few hundred iterations, the whole loop nest could take years to evaluate.
And the loops can be split across several constexpr function calls even.

The following patch adds another, slightly larger, limit on total number of
iterations in the whole loop nest.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2019-03-07  Jakub Jelinek  <jakub@redhat.com>

	PR c++/87481
	* doc/invoke.texi (-fconstexpr-loop-nest-limit=): Document.
	(-fconstexpr-loop-limit=): Slightly adjust wording.

	* c.opt (-fconstexpr-loop-nest-limit=): New option.
	(-fconstexpr-loop-limit=): Slightly adjust description.

	* constexpr.c (cxx_eval_loop_expr): Count also number of iterations
	of all nested loops and punt if it is above constexpr_loop_nest_limit.

	* g++.dg/cpp1y/constexpr-87481.C: New test.

--- gcc/doc/invoke.texi.jj	2019-03-02 09:03:25.822755663 +0100
+++ gcc/doc/invoke.texi	2019-03-07 14:25:34.881197149 +0100
@@ -210,7 +210,7 @@ in the following sections.
 @gccoptlist{-fabi-version=@var{n}  -fno-access-control @gol
 -faligned-new=@var{n}  -fargs-in-order=@var{n}  -fchar8_t  -fcheck-new @gol
 -fconstexpr-depth=@var{n}  -fconstexpr-loop-limit=@var{n} @gol
--fno-elide-constructors @gol
+-fconstexpr-loop-nest-limit=@var{n} -fno-elide-constructors @gol
 -fno-enforce-eh-specs @gol
 -fno-gnu-keywords @gol
 -fno-implicit-templates @gol
@@ -2522,10 +2522,19 @@ is 512.
 
 @item -fconstexpr-loop-limit=@var{n}
 @opindex fconstexpr-loop-limit
-Set the maximum number of iterations for a loop in C++14 constexpr functions
-to @var{n}.  A limit is needed to detect infinite loops during
+Set the maximum number of iterations for a single loop in C++14 constexpr
+functions to @var{n}.  A limit is needed to detect infinite loops during
 constant expression evaluation.  The default is 262144 (1<<18).
 
+@item -fconstexpr-loop-nest-limit=@var{n}
+@opindex fconstexpr-loop-nest-limit
+Set the maximum number of iterations for all loops in a loop nest in C++14
+constexpr functions to @var{n}.  Even when number of iterations of a single
+loop is limited with the above limit, if there are several nested loops and
+each of them has many iterations but still smaller than the above limit,
+the resulting evaluation of the loop nest might take too long.
+The default is 1048576 (1<<20).
+
 @item -fdeduce-init-list
 @opindex fdeduce-init-list
 Enable deduction of a template type parameter as
--- gcc/c-family/c.opt.jj	2019-02-25 23:56:58.149055806 +0100
+++ gcc/c-family/c.opt	2019-03-07 14:25:07.782639790 +0100
@@ -1414,7 +1414,11 @@ C++ ObjC++ Joined RejectNegative UIntege
 
 fconstexpr-loop-limit=
 C++ ObjC++ Joined RejectNegative UInteger Var(constexpr_loop_limit) Init(262144)
--fconstexpr-loop-limit=<number>	Specify maximum constexpr loop iteration count.
+-fconstexpr-loop-limit=<number>	Specify maximum constexpr loop iteration count of a single loop.
+
+fconstexpr-loop-nest-limit=
+C++ ObjC++ Joined RejectNegative UInteger Var(constexpr_loop_nest_limit) Init(1048576)
+-fconstexpr-loop-nest-limit=<number>	Specify maximum constexpr loop iteration count for all nested loops.
 
 fdebug-cpp
 C ObjC C++ ObjC++
--- gcc/cp/constexpr.c.jj	2019-03-06 19:45:40.360751756 +0100
+++ gcc/cp/constexpr.c	2019-03-07 14:03:00.040329107 +0100
@@ -4190,8 +4190,20 @@ cxx_eval_loop_expr (const constexpr_ctx
     default:
       gcc_unreachable ();
     }
+
+  /* True on entry to cxx_eval_loop_expr if called indirectly from another
+     cxx_eval_loop_expr.  */
+  static bool constexpr_loop_nested;
+
+  /* Number of evaluated loop iterations in the whole current loop nest.  */
+  static int constexpr_loop_nest_count;
+
+  bool save_constexpr_loop_nested = constexpr_loop_nested;
+  constexpr_loop_nested = true;
+
   hash_set<tree> save_exprs;
   new_ctx.save_exprs = &save_exprs;
+
   do
     {
       if (count != -1)
@@ -4248,6 +4260,24 @@ cxx_eval_loop_expr (const constexpr_ctx
 	  *non_constant_p = true;
 	  break;
 	}
+
+      /* In nested loops, don't count the first iteration, as it has been
+	 counted in the parent loop already.  */
+      if (count > (save_constexpr_loop_nested ? 1 : 0))
+	{
+	  if (++constexpr_loop_nest_count >= constexpr_loop_nest_limit)
+	    {
+	      if (!ctx->quiet)
+		error_at (cp_expr_loc_or_loc (t, input_location),
+			  "%<constexpr%> loop iteration count in all nested "
+			  "loops exceeds limit of %d (use "
+			  "-fconstexpr-loop-nest-limit= to increase the limit)",
+			  constexpr_loop_nest_limit);
+	      constexpr_loop_nest_count = 0;
+	      *non_constant_p = true;
+	      break;
+	    }
+	}
     }
   while (!returns (jump_target)
 	 && !breaks (jump_target)
@@ -4260,6 +4290,12 @@ cxx_eval_loop_expr (const constexpr_ctx
        iter != save_exprs.end(); ++iter)
     new_ctx.values->remove (*iter);
 
+  if (!save_constexpr_loop_nested)
+    {
+      constexpr_loop_nested = false;
+      constexpr_loop_nest_count = 0;
+    }
+
   return NULL_TREE;
 }
 
--- gcc/testsuite/g++.dg/cpp1y/constexpr-87481.C.jj	2019-03-07 14:28:45.664080874 +0100
+++ gcc/testsuite/g++.dg/cpp1y/constexpr-87481.C	2019-03-07 14:36:05.622894508 +0100
@@ -0,0 +1,16 @@
+// PR c++/87481
+// { dg-do compile { target c++14 } }
+// { dg-options "-fconstexpr-loop-limit=98304 -fconstexpr-loop-nest-limit=131072" } */
+
+constexpr unsigned
+foo ()
+{
+  unsigned int r = 0;
+  for (int i = 0; i < 65536; i++)
+    for (int j = 0; j < 65536; j++)
+      for (int k = 0; k < 65536; k++)	// { dg-error "'constexpr' loop iteration count in all nested loops exceeds limit of 131072" }
+	r += (i + j + k);
+  return r;
+}
+
+constexpr auto x = foo ();		// { dg-message "in 'constexpr' expansion of" }

	Jakub