c-family: Fix hang with -Wsequence-point [PR98126]

verify_sequence_points uses verify_tree to recursively walk the
subexpressions of an expression, and while recursing, it also
keeps lists of expressions found after/before a sequence point.
For a large expression, the list can grow significantly.  And
merge_tlist is at least N(n^2): for a list of length n it will
iterate n(n -1) times, and call candidate_equal_p each time, and
that can recurse further.  warn_for_collision also has to go
through the whole list.  With a large-enough expression, the
compilation can easily get stuck here for 24 hours.

This patch is a simple kludge: if we see that the expression is
overly complex, don't even try.

Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?

gcc/c-family/ChangeLog:

	PR c++/98126
	* c-common.c (verify_tree_lim_r): New function.
	(verify_sequence_points): Use it.  Use nullptr instead of 0.

gcc/testsuite/ChangeLog:

	PR c++/98126
	* g++.dg/warn/Wsequence-point-4.C: New test.
---
 gcc/c-family/c-common.c                       | 32 +++++++++--
 gcc/testsuite/g++.dg/warn/Wsequence-point-4.C | 53 +++++++++++++++++++
 2 files changed, 80 insertions(+), 5 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/warn/Wsequence-point-4.C


base-commit: df933e307b1950ce12472660dcac1765b8eb431d

On 12/4/20 10:40 PM, Marek Polacek wrote:
> verify_sequence_points uses verify_tree to recursively walk the
> subexpressions of an expression, and while recursing, it also
> keeps lists of expressions found after/before a sequence point.
> For a large expression, the list can grow significantly.  And
> merge_tlist is at least N(n^2): for a list of length n it will
> iterate n(n -1) times, and call candidate_equal_p each time, and
> that can recurse further.  warn_for_collision also has to go
> through the whole list.  With a large-enough expression, the
> compilation can easily get stuck here for 24 hours.
> 
> This patch is a simple kludge: if we see that the expression is
> overly complex, don't even try.
> 
> Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk?

OK.

> gcc/c-family/ChangeLog:
> 
> 	PR c++/98126
> 	* c-common.c (verify_tree_lim_r): New function.
> 	(verify_sequence_points): Use it.  Use nullptr instead of 0.
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR c++/98126
> 	* g++.dg/warn/Wsequence-point-4.C: New test.
> ---
>   gcc/c-family/c-common.c                       | 32 +++++++++--
>   gcc/testsuite/g++.dg/warn/Wsequence-point-4.C | 53 +++++++++++++++++++
>   2 files changed, 80 insertions(+), 5 deletions(-)
>   create mode 100644 gcc/testsuite/g++.dg/warn/Wsequence-point-4.C
> 
> diff --git a/gcc/c-family/c-common.c b/gcc/c-family/c-common.c
> index dda23520b96..0b348aec77b 100644
> --- a/gcc/c-family/c-common.c
> +++ b/gcc/c-family/c-common.c
> @@ -2056,23 +2056,45 @@ verify_tree (tree x, struct tlist **pbefore_sp, struct tlist **pno_sp,
>       }
>   }
>   
> +static constexpr size_t verify_sequence_points_limit = 1024;
> +
> +/* Called from verify_sequence_points via walk_tree.  */
> +
> +static tree
> +verify_tree_lim_r (tree *tp, int *walk_subtrees, void *data)
> +{
> +  if (++*((size_t *) data) > verify_sequence_points_limit)
> +    return integer_zero_node;
> +
> +  if (TYPE_P (*tp))
> +    *walk_subtrees = 0;
> +
> +  return NULL_TREE;
> +}
> +
>   /* Try to warn for undefined behavior in EXPR due to missing sequence
>      points.  */
>   
>   void
>   verify_sequence_points (tree expr)
>   {
> -  struct tlist *before_sp = 0, *after_sp = 0;
> +  tlist *before_sp = nullptr, *after_sp = nullptr;
> +
> +  /* verify_tree is highly recursive, and merge_tlist is O(n^2),
> +     so we return early if the expression is too big.  */
> +  size_t n = 0;
> +  if (walk_tree (&expr, verify_tree_lim_r, &n, nullptr))
> +    return;
>   
> -  warned_ids = 0;
> -  save_expr_cache = 0;
> -  if (tlist_firstobj == 0)
> +  warned_ids = nullptr;
> +  save_expr_cache = nullptr;
> +  if (!tlist_firstobj)
>       {
>         gcc_obstack_init (&tlist_obstack);
>         tlist_firstobj = (char *) obstack_alloc (&tlist_obstack, 0);
>       }
>   
> -  verify_tree (expr, &before_sp, &after_sp, 0);
> +  verify_tree (expr, &before_sp, &after_sp, NULL_TREE);
>     warn_for_collisions (after_sp);
>     obstack_free (&tlist_obstack, tlist_firstobj);
>   }
> diff --git a/gcc/testsuite/g++.dg/warn/Wsequence-point-4.C b/gcc/testsuite/g++.dg/warn/Wsequence-point-4.C
> new file mode 100644
> index 00000000000..1382ab5a934
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/warn/Wsequence-point-4.C
> @@ -0,0 +1,53 @@
> +// PR c++/98126
> +// { dg-do compile }
> +// { dg-options "-Wsequence-point" }
> +// Make sure we don't hand when verify_tree processes a large expression.
> +
> +struct T { bool operator==(const T &ot) const; };
> +
> +#define CMP(M, N, L) t[100 * M + 10 * N + L] == ot.t[100 * M + 10 * N + L] &&
> +
> +#define CMP1(M, N) \
> +  CMP(M, N, 0) \
> +  CMP(M, N, 1) \
> +  CMP(M, N, 2) \
> +  CMP(M, N, 3) \
> +  CMP(M, N, 4) \
> +  CMP(M, N, 5) \
> +  CMP(M, N, 6) \
> +  CMP(M, N, 7) \
> +  CMP(M, N, 8) \
> +  CMP(M, N, 9)
> +
> +#define CMP2(M) \
> +  CMP1(M, 0) \
> +  CMP1(M, 1) \
> +  CMP1(M, 2) \
> +  CMP1(M, 3) \
> +  CMP1(M, 4) \
> +  CMP1(M, 5) \
> +  CMP1(M, 6) \
> +  CMP1(M, 7) \
> +  CMP1(M, 8) \
> +  CMP1(M, 9)
> +
> +#define GENERATE_CMPS \
> +  CMP2(0) \
> +  CMP2(1) \
> +  CMP2(2) \
> +  CMP2(3) \
> +  CMP2(4) \
> +  CMP2(5) \
> +  CMP2(6) \
> +  CMP2(7) \
> +  CMP2(8) \
> +  CMP2(9)
> +
> +struct C {
> +  bool operator==(const C &ot) const {
> +    return
> +      GENERATE_CMPS
> +      true;
> +  }
> +  T t[999];
> +};
> 
> base-commit: df933e307b1950ce12472660dcac1765b8eb431d
>