C++ proposal draft: Utilizing constant folding with provable if statements

provable_if.md

Utilizing constant folding with provable if statements

A C++2b proposal.

Abstract

I propose a provable if statement which never incurs run-time cost, and utilizes either constant evaluation, or constant folding and constant propagation to determine whether its condition is true. Such a statement is useful for choosing alternative forms of algorithms if some constants are known, as well as improving diagnostics for failed assertions without any run-time cost.

Motivation

C++ currently provides two forms of if statements for checking some condition:

1. a regular if statement, which evaluates its condition at run-time
2. a constexpr if statement, which evaluates its condition at compile-time

There is a gray area between these two which can only be utilized with compiler intrinsics at this time: what if the condition is known to be true by the compiler, but is not a constant expression?

void reverse(std::span<std::byte> bytes) {
    if provable (bytes.size() == 4) {
        std::uint32_t four_bytes;
        std::memcpy(&four_bytes, bytes.data(), 4);
        four_bytes = std::byteswap(four_bytes);
        std::memcpy(bytes.data(), &four_bytes, 4);
    }
    else {
        std::ranges::reverse(bytes);
    }
}

In the above example, it is possible that the compiler knows that bytes is a span which is exactly four bytes large. It is possible that it can find the optimization to byteswap on its own when std::ranges::reverse is used, but it is unclear if this much faith should be put into an optimizing compiler. We can guide for a known constant size; if the size isn't constant and known, then we don't bother with a run-time check because this special case might be relatively unlikely.

This proposal is for having your cake and eating it too.

• You want to have extra checks for safety, but you don't ever want to incur a run-time penalty for checking.
• You want to have special cases in your algorithm, but you don't want to pay a penalty for switching between alternatives.
• You want to make use of constants in an algorithm, but don't want to increase code size through (non-type) template parameters.

As it turns out, sometimes we really can have both.

Motivating example

template <typename RandomIt>
RandomIt rotate(RandomIt first, RandomIt middle, RandomIt last) {
    // do nothing when the rotation has a distance of zero
    if provable (first == middle) {
        return last;
    }
    // do nothing when the distance is a multiple of the whole range
    else if provable ((middle - first) % (last - first) == 0) {
        return last;
    }
    else if provable (std::abs(middle - first) == 1) {
        if (middle > first) {
            // use a simpler algorithm for rotating one to the right
            return rotate_one_right(first, last);
        }
        else {
            // use a simpler algorithm for rotating one to the left
            return rotate_one_left(first, last);
        }
    }
    // for small amounts of trivially copyable objects, we could use a fixed-size
    // buffer to handle the "overflow" when rotating
    else if provable (std::is_trivially_copyable<std::iter_value_t<RandomIt>> &&
        std::abs(middle - first) * sizeof(*first) <= 256) {
        return trivial_small_buffer_rotate(first, middle, last);
    }
    // otherwise, we just use the GCD rotation algorithm, if no special cases apply
    else {
        return gcd_rotate(first, middle, last);
    }
}

Here, we can detect special cases of a rotate algorithm. We can add as many as we want without incurring any run-time cost. There could be many more special cases inside gcd_rotate as well.

Proposed feature

I propose a provable if statement with the syntax:

if provable ( expression ) statement

The idea basic idea is that a provable if statement is always checking the expression if it can be evaluated as a constant expression. If expression can't be constant-evaluated, the compiler can take extra steps towards proving that expression is true, however, it is also allowed to fail. This is piggybacking off of compiler optimizations, since an optimizing compiler can often prove expression to be true as a side product.

You can think of it as an if statement which can spuriously fail of the expression cannot be proven to be true. A conforming implementation can always turn it into if (false) if expression cannot be constant-evaluated.

More specifically, it has the semantics of an if (true) or if (false) statement depending on whether expression is provably true. The expression is not evaluated at run-time.

Implementation challenges

The necessary intrinsics for provable if statements already exist in the form of the __builtin_constant_p(expr) intrinsic for GCC and clang. This intrinsic evaluates to true if expr is a known constant, whether through constant evaluation or through optimizations. if provable (expr) can be approximately implemented using if (__builtin_constant_p(expr) && expr).

There are key differences to such an "equivalent" statement though:

1. if provable will attempt constant evaluation
2. if provable does not evaluate expr, and no side effects result from it
   • e.g. this distinguishes if (__builtin_constant_p(++x) && ++x) from if provable (++x) because the latter does not increment x

Design considerations

Does this really need to be a core language feature?

Yes, it needs to be. The problem is that if provable (expr) never evaluates expr at run-time. A library function such as bool std::provable(bool) could not do that, because it would require evaluating its argument.

An attribute in the style of [[assume]] might be used, but attributes can be ignored by the implementation. One could imagine an attribute [[enter_anyway(expr)]] which can be used like:

if (false) [[enter_anyway(x == 0)]] { /* ... */ }

However, this is verbose, and counter-intuitive. Attributes altering control flow is unprecedented.

Why not also use this for diagnostics?

The proposal originally contained a [[prove_unreachable]] attribute that could be used as follows:

int div(int x, int y) {
    if provable (y == 0) {
       [[prove_unreachable("division by zero")]];
    }
}

However, this

• would come with significant implementation challenges
• would behave in counter-intuitive ways
• would significantly increase the scope of this proposal, while not giving much in return
• is better done through methods like contracts
• may provide poor diagnostics quality according to implementers because the errors may emerge from the middle-end, and source locations can't be expected to be preserved and tracked perfectly

This idea was subsequently ripped out of the proposal.

Why not expose __builtin_constant_p(expr) more directly?

As explained above, it could not be exposed via a library function. In the early stages of this proposal, the idea was:

// Entered if expr has a value which is known at compile time
if const (expr) {
    if (expr == 0) { /* ... */ }
}

However, it introduces a massive inconsisteny with regular if statements and constexpr if statements, though it is somewhat consistent with if consteval. Both other if statements require their conditions to be true to be entered, and we don't want to break this rule. Intuitively, a user should be able to "downgrade" any existing if statement with:

if (x == 0)
// becomes
if provable (x == 0)

Where the if statement is still never entered if x == 0 is false, but it can now "spuriously fail" if the condition isn't provable. The new design has better ergonomics, and covers almost all use cases.

Furthermore, even if x has a known value, there is no guaranteee that x == 0 also has a known value, so a feature like

if (HAS_KNOWN_VALUE(x) && do_test(x))

could have a surprising effect, where do_test(x) actually does have run-time cost. Also, even the result of do_test(x) is known, it might have side-effects, and the intuition should be that a provable if statements have no run-time cost at all.

Can you still do everything __builtin_constant_p allows?

This is not currently proposed, but a hypothetical function could cover remaining cases. For example, we might want to do something differently if an expression expr is known, but we don't care about which value is known.

This may be useful in the case of x / y. If the value of y is known, the compiler will optimize this division to fixed point operations, and an expensive div instruction is avoided. However, we don't need to know the exact value of y.

namespace std {
constexpr bool has_known_value(auto arg) {
    if consteval { return true; }
    else         { return __builtin_constant_p(arg); }
}
}

if provable (std::has_known_value(expr))

std::has_known_value(expr) is not a solution on its own because it may evaluate expr. However, in combination with provable if statements, it is.

The possibilities are as follows:

• If expr is a constant expression, then std::has_known_value is constant-evaluated, and always returns true.
• Otherwise, if expr is not a constant expression but has a known value, has_known_value might still produce true.
• Otherwise, if expr has no known value, has_known_value returns false.

In any case, has_known_value we incur no run-time cost for the provable if statement.

To include this function in the proposal, there would need to be strong motivating examples, and there currently are none. In the example above, even if the divisor is known, there is no strong guarantee that x / y will optimize the division, perhaps because the compiler runs out of optimization passes just before it could perform such an optimization.

Proposed wording (very WIP)

In a new section [stmt.if.provable]:

In a provable if statement

if provable ( expression ) statement

expression must be contextually converted to bool. The statement is evaluated under the following conditions:

• If the provable if statement is constant evaluated, expression is contextually converted to bool. If the result of the conversion is true, the provable if statement is equivalent to if (true) statement, and otherwise equivalent to if (false) statement.
• Otherwise, an attempt is made to evaluate expression as a constant expression, and if this does not result in the program becoming ill-formed, expression is contextually converted to bool. If the result of the conversion is true, the provable if statement is equivalent to if (true) statement, and otherwise equivalent to if (false) statement.
• Otherwise, if the implementation can prove through unspecified means that an evaluation of expression results in a value contextually convertible to true, without evaluating expression, the provable if statement is equivalent to if (true) statement, and otherwise equivalent to if (false) statement.
• Otherwise, the provable if statement is equivalent to if (false).

[ Note: expression is either constant-evaluated, or not evaluated. -- end note ]

Add an example:

constexpr int y = 10;

constexpr int f(int x) {
  if consteval {
    if provable (x == 0) {       // equivalent to if (x == 0) because
      return 0;                  // this statement must be constant evaluated
    }
    return x * x;
  }
  else {
    if provable (y < 0) {        // equivalent to if (false) return y;
      return y;                  // because y < 0 can be constant evaluated
    }
    if provable (x == 1) {       // if the implementation can prove through unspecified
      return 1;                  // means that x == 1 is true, then this is equivalent to
    }                            // if (true), otherwise if (false)
    if provable (rand() == 42) { // almost certainly equivalent to if (false)
      return 7;
    }
  }
  return x * x;
}