Re: [PATCH] c++: Implement C++26 P2809R3 - Trivial infinite loops are not Undefined Behavior

[Richard Biener <richard.guenther@gmail.com>]

On Wed, Apr 3, 2024 at 9:25 AM Jakub Jelinek <jakub@redhat.com> wrote:
>
> Hi!
>
> The following patch attempts to implement P2809R3, which has been voted
> in as a DR.
>
> The middle-end has its behavior documented:
> '-ffinite-loops'
>      Assume that a loop with an exit will eventually take the exit and
>      not loop indefinitely.  This allows the compiler to remove loops
>      that otherwise have no side-effects, not considering eventual
>      endless looping as such.
>
>      This option is enabled by default at '-O2' for C++ with -std=c++11
>      or higher.
>
> So, the following patch attempts to detect trivial infinite loops and
> turn their conditions into INTEGER_CSTs so that they don't really have
> exits in the middle-end and so regardless of -ffinite-loops or
> -fno-finite-loops they are handled as infinite loops by the middle-end.
> Otherwise, if the condition would be a large expression calling various
> constexpr functions, I'd be afraid we could e.g. just inline some of them
> and not all of them and the middle-end could still see tests in the
> condition and with -ffinite-loops optimize it by assuming that such loops
> need to be finite.
>
> The "A trivial infinite loop is a trivially empty iteration statement for
> which the converted controlling expression is a constant expression, when
> interpreted as a constant-expression ([expr.const]), and evaluates to true."
> wording isn't clear to me what it implies for manifest constant evaluation
> of the expression, especially given the
> int x = 42;
> while (std::is_constant_evaluated() || --x) ;
> example in the rationale.
>
> The patch assumes that the condition expression aren't manifestly constant
> evaluated.  If it would be supposed to be manifestly constant evaluated,
> then I think the DR would significantly change behavior of existing programs
> and have really weird effects.  Before the DR has been voted in, I think
> void foo (int x)
> {
>   if (x == 0)
>     while (std::is_constant_evaluated())
>       ;
>   else
>     while (!std::is_constant_evaluated())
>       ;
> }
> would have well defined behavior of zero loop body iterations if x == 0 and
> undefined behavior otherwise.  If the condition expression is manifestly
> constant evaluated if it evaluates to true, and otherwise can be
> non-constant or not manifestly constant evaluated otherwise, then the
> behavior would be that for x == 0 it is well defined trvial infinite loop,
> while for x != 0 it would keep to be undefined behavior (infinite loop,
> as !std::is_constant_evaluated() is false when manifestly constant evaluated
> and if we keep the condition as is, evaluates then to true.  I think it
> would be fairly strange if both loops are infinite even when their condition
> are negated.  Similar for anything that is dependent on if consteval or
> std::is_constant_evaluated() inside of it.
>
> So, the patch below attempts to discover trivially empty iteration
> statements at cp_fold time if it is the final mce_false folding,
> attempts to maybe_constant_value with mce_false evaluate the conditions
> and replaces it with the returned value if constant non-zero.
>
> The testcases then try to check if the FE changed the calls in the
> conditions into constants.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

I'll note that -ffinite-loops is reflected into the IL (the loop structure) at
CFG build time in the following simple way:

      /* Push the global flag_finite_loops state down to individual loops.  */
      loop->finite_p = flag_finite_loops;

and the "has an exit" is checked when we evalutate a loop->finite_p loop.
The above flag evaluation could be made a langhook as it's suitably
early, but I'm not sure whether that would help.   The flag is evaluated
when we evaluate the loop ANNOTATE_EXPRs, so annotating finite
loops with a new annotate might be possible as well.

Just in case making the control expression constant to the middle-end
doesn't scale.

Richard.

> Or is it really supposed to be mce_true with the above described weird
> behavior?  If so, I think the standard at least should mention it in Annex C
> (though, where when it is a DR?).
>
> 2024-04-02  Jakub Jelinek  <jakub@redhat.com>
>
>         PR c++/114462
>         * cp-gimplify.cc (cp_fold): Implement C++26 P2809R3 - Trivial infinite
>         loops are not Undefined Behavior.  For trivially empty WHILE_STMT,
>         DO_STMT or FOR_STMT iteration statements check if the condition is
>         constant expression which evaluates to true and in that case replace
>         the condition with true.
>
>         * g++.dg/cpp26/trivial-infinite-loop1.C: New test.
>         * g++.dg/cpp26/trivial-infinite-loop2.C: New test.
>         * g++.dg/cpp26/trivial-infinite-loop3.C: New test.
>
> --- gcc/cp/cp-gimplify.cc.jj    2024-03-23 11:17:06.958445857 +0100
> +++ gcc/cp/cp-gimplify.cc       2024-04-02 11:27:56.069170914 +0200
> @@ -3527,6 +3527,78 @@ cp_fold (tree x, fold_flags_t flags)
>        x = evaluate_requires_expr (x);
>        break;
>
> +    case WHILE_STMT:
> +      /* For trivially empty iteration statements check if the condition
> +        is constant expression which evaluates to true and in that case
> +        change the condition to the constant, so that the middle-end treats
> +        it as an infinite loop regardless of -ffinite-loops.  */
> +      if ((flags & ff_mce_false) && !integer_nonzerop (WHILE_COND (x)))
> +       {
> +         tree body = WHILE_BODY (x);
> +         if (expr_first (body) == NULL_TREE)
> +           {
> +             r = maybe_constant_value (WHILE_COND (x), /*decl=*/NULL_TREE,
> +                                       mce_false);
> +             if (integer_nonzerop (r))
> +               {
> +                 x = copy_node (x);
> +                 WHILE_COND (x) = r;
> +                 break;
> +               }
> +           }
> +       }
> +      return org_x;
> +
> +    case DO_STMT:
> +      /* For trivially empty iteration statements check if the condition
> +        is constant expression which evaluates to true and in that case
> +        change the condition to the constant, so that the middle-end treats
> +        it as an infinite loop regardless of -ffinite-loops.  */
> +      if ((flags & ff_mce_false) && !integer_nonzerop (DO_COND (x)))
> +       {
> +         tree body = DO_BODY (x);
> +         if (expr_first (body) == NULL_TREE
> +             || (CONVERT_EXPR_P (body)
> +                 && integer_zerop (TREE_OPERAND (body, 0))
> +                 && VOID_TYPE_P (TREE_TYPE (body))))
> +           {
> +             r = maybe_constant_value (DO_COND (x), /*decl=*/NULL_TREE,
> +                                       mce_false);
> +             if (integer_nonzerop (r))
> +               {
> +                 x = copy_node (x);
> +                 DO_COND (x) = r;
> +                 break;
> +               }
> +           }
> +       }
> +      return org_x;
> +
> +    case FOR_STMT:
> +      /* For trivially empty iteration statements check if the condition
> +        is constant expression which evaluates to true and in that case
> +        change the condition to the constant, so that the middle-end treats
> +        it as an infinite loop regardless of -ffinite-loops.  */
> +      if ((flags & ff_mce_false)
> +         && FOR_COND (x)
> +         && FOR_EXPR (x) == NULL_TREE
> +         && !integer_nonzerop (FOR_COND (x)))
> +       {
> +         tree body = FOR_BODY (x);
> +         if (expr_first (body) == NULL_TREE)
> +           {
> +             r = maybe_constant_value (FOR_COND (x), /*decl=*/NULL_TREE,
> +                                       mce_false);
> +             if (integer_nonzerop (r))
> +               {
> +                 x = copy_node (x);
> +                 FOR_COND (x) = r;
> +                 break;
> +               }
> +           }
> +       }
> +      return org_x;
> +
>      default:
>        return org_x;
>      }
> --- gcc/testsuite/g++.dg/cpp26/trivial-infinite-loop1.C.jj      2024-04-02 11:50:00.943874185 +0200
> +++ gcc/testsuite/g++.dg/cpp26/trivial-infinite-loop1.C 2024-04-02 12:19:52.132211449 +0200
> @@ -0,0 +1,150 @@
> +// P2809R3 - Trivial infinite loops are not Undefined Behavior
> +// { dg-do compile { target c++11 } }
> +// { dg-additional-options "-fdump-tree-gimple -fno-inline" }
> +// { dg-final { scan-tree-dump-not " = foo \\\(\\\)" "gimple" } }
> +// { dg-final { scan-tree-dump-not " = S::operator bool \\\(" "gimple" } }
> +// { dg-final { scan-tree-dump-not " = baz \\\(\\\)" "gimple" } }
> +// { dg-final { scan-tree-dump-not " = std::is_constant_evaluated \\\(\\\)" "gimple" } }
> +
> +volatile int v;
> +
> +constexpr bool
> +foo ()
> +{
> +  return true;
> +}
> +
> +struct S
> +{
> +  constexpr S () : s (true) {}
> +  constexpr operator bool () const { return s; }
> +  bool s;
> +};
> +
> +#if __cplusplus >= 202002L
> +namespace std {
> +  constexpr inline bool
> +  is_constant_evaluated () noexcept
> +  {
> +#if __cpp_if_consteval >= 202106L
> +    if consteval { return true; } else { return false; }
> +#else
> +    return __builtin_is_constant_evaluated ();
> +#endif
> +  }
> +}
> +
> +constexpr bool
> +baz ()
> +{
> +  return !std::is_constant_evaluated ();
> +}
> +#endif
> +
> +void
> +bar (int x)
> +{
> +  switch (x)
> +    {
> +    case 0:
> +      while (foo ()) ;
> +      break;
> +    case 1:
> +      while (foo ()) {}
> +      break;
> +    case 2:
> +      do ; while (foo ());
> +      break;
> +    case 3:
> +      do {} while (foo ());
> +      break;
> +    case 4:
> +      for (v = 42; foo (); ) ;
> +      break;
> +    case 5:
> +      for (v = 42; foo (); ) {}
> +      break;
> +    case 6:
> +      for (int w = 42; foo (); ) ;
> +      break;
> +    case 7:
> +      for (int w = 42; foo (); ) {}
> +      break;
> +    case 10:
> +      while (S {}) ;
> +      break;
> +    case 11:
> +      while (S {}) {}
> +      break;
> +    case 12:
> +      do ; while (S {});
> +      break;
> +    case 13:
> +      do {} while (S {});
> +      break;
> +    case 14:
> +      for (v = 42; S {}; ) ;
> +      break;
> +    case 15:
> +      for (v = 42; S {}; ) {}
> +      break;
> +    case 16:
> +      for (int w = 42; S {}; ) ;
> +      break;
> +    case 17:
> +      for (int w = 42; S {}; ) {}
> +      break;
> +#if __cplusplus >= 202002L
> +    case 20:
> +      while (baz ()) ;
> +      break;
> +    case 21:
> +      while (baz ()) {}
> +      break;
> +    case 22:
> +      do ; while (baz ());
> +      break;
> +    case 23:
> +      do {} while (baz ());
> +      break;
> +    case 24:
> +      for (v = 42; baz (); ) ;
> +      break;
> +    case 25:
> +      for (v = 42; baz (); ) {}
> +      break;
> +    case 26:
> +      for (int w = 42; baz (); ) ;
> +      break;
> +    case 27:
> +      for (int w = 42; baz (); ) {}
> +      break;
> +    case 30:
> +      while (!std::is_constant_evaluated ()) ;
> +      break;
> +    case 31:
> +      while (!std::is_constant_evaluated ()) {}
> +      break;
> +    case 32:
> +      do ; while (!std::is_constant_evaluated ());
> +      break;
> +    case 33:
> +      do {} while (!std::is_constant_evaluated ());
> +      break;
> +    case 34:
> +      for (v = 42; !std::is_constant_evaluated (); ) ;
> +      break;
> +    case 35:
> +      for (v = 42; !std::is_constant_evaluated (); ) {}
> +      break;
> +    case 36:
> +      for (int w = 42; !std::is_constant_evaluated (); ) ;
> +      break;
> +    case 37:
> +      for (int w = 42; !std::is_constant_evaluated (); ) {}
> +      break;
> +#endif
> +    default:
> +      break;
> +    }
> +}
> --- gcc/testsuite/g++.dg/cpp26/trivial-infinite-loop2.C.jj      2024-04-02 12:06:31.494215751 +0200
> +++ gcc/testsuite/g++.dg/cpp26/trivial-infinite-loop2.C 2024-04-02 12:20:32.037663398 +0200
> @@ -0,0 +1,150 @@
> +// P2809R3 - Trivial infinite loops are not Undefined Behavior
> +// { dg-do compile { target c++11 } }
> +// { dg-additional-options "-fdump-tree-gimple -fno-inline" }
> +// { dg-final { scan-tree-dump-times " = foo \\\(\\\)" 8 "gimple" } }
> +// { dg-final { scan-tree-dump-times " = S::operator bool \\\(" 8 "gimple" } }
> +// { dg-final { scan-tree-dump-times " = baz \\\(\\\)" 8 "gimple" { target c++20 } } }
> +// { dg-final { scan-tree-dump-times " = std::is_constant_evaluated \\\(\\\)" 9 "gimple" { target c++20 } } }
> +
> +volatile int v;
> +
> +constexpr bool
> +foo ()
> +{
> +  return false;
> +}
> +
> +struct S
> +{
> +  constexpr S () : s (false) {}
> +  constexpr operator bool () const { return s; }
> +  bool s;
> +};
> +
> +#if __cplusplus >= 202002L
> +namespace std {
> +  constexpr inline bool
> +  is_constant_evaluated () noexcept
> +  {
> +#if __cpp_if_consteval >= 202106L
> +    if consteval { return true; } else { return false; }
> +#else
> +    return __builtin_is_constant_evaluated ();
> +#endif
> +  }
> +}
> +
> +constexpr bool
> +baz ()
> +{
> +  return std::is_constant_evaluated ();
> +}
> +#endif
> +
> +void
> +bar (int x)
> +{
> +  switch (x)
> +    {
> +    case 0:
> +      while (foo ()) ;
> +      break;
> +    case 1:
> +      while (foo ()) {}
> +      break;
> +    case 2:
> +      do ; while (foo ());
> +      break;
> +    case 3:
> +      do {} while (foo ());
> +      break;
> +    case 4:
> +      for (v = 42; foo (); ) ;
> +      break;
> +    case 5:
> +      for (v = 42; foo (); ) {}
> +      break;
> +    case 6:
> +      for (int w = 42; foo (); ) ;
> +      break;
> +    case 7:
> +      for (int w = 42; foo (); ) {}
> +      break;
> +    case 10:
> +      while (S {}) ;
> +      break;
> +    case 11:
> +      while (S {}) {}
> +      break;
> +    case 12:
> +      do ; while (S {});
> +      break;
> +    case 13:
> +      do {} while (S {});
> +      break;
> +    case 14:
> +      for (v = 42; S {}; ) ;
> +      break;
> +    case 15:
> +      for (v = 42; S {}; ) {}
> +      break;
> +    case 16:
> +      for (int w = 42; S {}; ) ;
> +      break;
> +    case 17:
> +      for (int w = 42; S {}; ) {}
> +      break;
> +#if __cplusplus >= 202002L
> +    case 20:
> +      while (baz ()) ;
> +      break;
> +    case 21:
> +      while (baz ()) {}
> +      break;
> +    case 22:
> +      do ; while (baz ());
> +      break;
> +    case 23:
> +      do {} while (baz ());
> +      break;
> +    case 24:
> +      for (v = 42; baz (); ) ;
> +      break;
> +    case 25:
> +      for (v = 42; baz (); ) {}
> +      break;
> +    case 26:
> +      for (int w = 42; baz (); ) ;
> +      break;
> +    case 27:
> +      for (int w = 42; baz (); ) {}
> +      break;
> +    case 30:
> +      while (std::is_constant_evaluated ()) ;
> +      break;
> +    case 31:
> +      while (std::is_constant_evaluated ()) {}
> +      break;
> +    case 32:
> +      do ; while (std::is_constant_evaluated ());
> +      break;
> +    case 33:
> +      do {} while (std::is_constant_evaluated ());
> +      break;
> +    case 34:
> +      for (v = 42; std::is_constant_evaluated (); ) ;
> +      break;
> +    case 35:
> +      for (v = 42; std::is_constant_evaluated (); ) {}
> +      break;
> +    case 36:
> +      for (int w = 42; std::is_constant_evaluated (); ) ;
> +      break;
> +    case 37:
> +      for (int w = 42; std::is_constant_evaluated (); ) {}
> +      break;
> +#endif
> +    default:
> +      break;
> +    }
> +}
> --- gcc/testsuite/g++.dg/cpp26/trivial-infinite-loop3.C.jj      2024-04-02 12:14:23.993717999 +0200
> +++ gcc/testsuite/g++.dg/cpp26/trivial-infinite-loop3.C 2024-04-02 12:21:10.341137353 +0200
> @@ -0,0 +1,151 @@
> +// P2809R3 - Trivial infinite loops are not Undefined Behavior
> +// { dg-do compile { target c++11 } }
> +// { dg-additional-options "-fdump-tree-gimple -fno-inline" }
> +// { dg-final { scan-tree-dump-times " = foo \\\(\\\)" 8 "gimple" } }
> +// { dg-final { scan-tree-dump-times " = S::operator bool \\\(" 8 "gimple" } }
> +// { dg-final { scan-tree-dump-times " = baz \\\(\\\)" 8 "gimple" { target c++20 } } }
> +// { dg-final { scan-tree-dump-times " = std::is_constant_evaluated \\\(\\\)" 9 "gimple" { target c++20 } } }
> +
> +volatile int v;
> +int y;
> +
> +constexpr bool
> +foo ()
> +{
> +  return true;
> +}
> +
> +struct S
> +{
> +  constexpr S () : s (true) {}
> +  constexpr operator bool () const { return s; }
> +  bool s;
> +};
> +
> +#if __cplusplus >= 202002L
> +namespace std {
> +  constexpr inline bool
> +  is_constant_evaluated () noexcept
> +  {
> +#if __cpp_if_consteval >= 202106L
> +    if consteval { return true; } else { return false; }
> +#else
> +    return __builtin_is_constant_evaluated ();
> +#endif
> +  }
> +}
> +
> +constexpr bool
> +baz ()
> +{
> +  return !std::is_constant_evaluated ();
> +}
> +#endif
> +
> +void
> +bar (int x)
> +{
> +  switch (x)
> +    {
> +    case 0:
> +      while (foo ()) ++y;
> +      break;
> +    case 1:
> +      while (foo ()) { ++y; }
> +      break;
> +    case 2:
> +      do ++y; while (foo ());
> +      break;
> +    case 3:
> +      do { ++y; } while (foo ());
> +      break;
> +    case 4:
> +      for (v = 42; foo (); ) ++y;
> +      break;
> +    case 5:
> +      for (v = 42; foo (); ) { ++y; }
> +      break;
> +    case 6:
> +      for (int w = 42; foo (); ) ++y;
> +      break;
> +    case 7:
> +      for (int w = 42; foo (); ) { ++y; }
> +      break;
> +    case 10:
> +      while (S {}) ++y;
> +      break;
> +    case 11:
> +      while (S {}) { ++y; }
> +      break;
> +    case 12:
> +      do ++y; while (S {});
> +      break;
> +    case 13:
> +      do { ++y; } while (S {});
> +      break;
> +    case 14:
> +      for (v = 42; S {}; ) ++y;
> +      break;
> +    case 15:
> +      for (v = 42; S {}; ) { ++y; }
> +      break;
> +    case 16:
> +      for (int w = 42; S {}; ) ++y;
> +      break;
> +    case 17:
> +      for (int w = 42; S {}; ) { ++y; }
> +      break;
> +#if __cplusplus >= 202002L
> +    case 20:
> +      while (baz ()) ++y;
> +      break;
> +    case 21:
> +      while (baz ()) { ++y; }
> +      break;
> +    case 22:
> +      do ++y; while (baz ());
> +      break;
> +    case 23:
> +      do { ++y; } while (baz ());
> +      break;
> +    case 24:
> +      for (v = 42; baz (); ) ++y;
> +      break;
> +    case 25:
> +      for (v = 42; baz (); ) { ++y; }
> +      break;
> +    case 26:
> +      for (int w = 42; baz (); ) ++y;
> +      break;
> +    case 27:
> +      for (int w = 42; baz (); ) { ++y; }
> +      break;
> +    case 30:
> +      while (!std::is_constant_evaluated ()) ++y;
> +      break;
> +    case 31:
> +      while (!std::is_constant_evaluated ()) { ++y; }
> +      break;
> +    case 32:
> +      do ++y; while (!std::is_constant_evaluated ());
> +      break;
> +    case 33:
> +      do { ++y; } while (!std::is_constant_evaluated ());
> +      break;
> +    case 34:
> +      for (v = 42; !std::is_constant_evaluated (); ) ++y;
> +      break;
> +    case 35:
> +      for (v = 42; !std::is_constant_evaluated (); ) { ++y; }
> +      break;
> +    case 36:
> +      for (int w = 42; !std::is_constant_evaluated (); ) ++y;
> +      break;
> +    case 37:
> +      for (int w = 42; !std::is_constant_evaluated (); ) { ++y; }
> +      break;
> +#endif
> +    default:
> +      break;
> +    }
> +}
>
>         Jakub
>