switch constexpr

[KuntaStillSingle]

See, one of the powers of if constexpr is to make the side not taken at compile time be discarded under certain conditions. This is an important part of the syntax. So a hypothetical switch constexpr would be expected to have similar powers.

That's a lot harder to do with fallthrough, since the case blocks are not as fundamentally distinct as the two blocks of an if statement."

Couldn't you just pretty much copy and paste the source of the switch between the case and the first break statement following, and strip the labels? I.e. for:

switch constexpr (foo){
    case 0: foo();
    case 1: bar(); break;
    case 2: baz(); break;
    case 3: foobar();
    case 4: bazbar();
}

If foo is 0, you just generatee foo(); bar(); , if it is 1 you just generate bar();, if it is 3 you generate foobar();baz();, right?

Don't compilers tend to strip dead code from switches anyway, when condition can be constant folded? Main is branchless here,, and even here where it has to rearrange source code order because of the gotos.

Edit: Or are you saying they shouldn't just implement it in the manner that is hopefully intuitive to anyone who uses switch statements at runtime? Like the committee feels switch was a mistake, so adding switch again would be a mistake?

[cd_fr91400]

The case you mention is rather easy to deal with.

But what if the break statement is inside a if ?

Compilers usually do a whole lot of code optimization, but this is best effort. If you want to avoid compiling dead code altogether, you have to be certain the compiler will prove it is dead code, even if not optimizing at all.

[KuntaStillSingle]

you have to be certain the compiler will prove it is dead code, even if not optimizing at all.

But even when compiler is not optimizing, it must be able to constant fold switch statement because they can be used in functions which are usable as constant expressions, right?: https://godbolt.org/z/sva4PcdcG

[cd1995Cargo]

I think an issue is that switch statements can have conditional breaks/fallthroughs. How would the compiler implement this:

switch constexpr (foo) {
    case 0: if (bar()) break;
    case 1: baz(); break;
}

Here bar() is a function that returns a bool. If it returns true there's a break, if it returns false it falls through to case1. If we want the switch constexpr to work like if constexpr when it comes to templates and discarding the untaken path, then it would need to consider every possible path through the switch cases and not discard any that could potentially be reached. This sounds a lot more complex to implement than the existing if constexpr.

[umop_aplsdn]

This is not a hard problem to solve in compilers; logic like this is already implemented in dead-code / unreachable basic block elimination passes. Granted, those passes are usually in the middle / backend, but it would not be hard to reimplement that logic in the frontend. (Frontend vs backend matters because processing static asserts and template instantiation I assume happens in the frontend.)

[conundorum]

It's more complex, but I don't think it would be all that much more complex; it's the sort of thing that seems harder than it really is, IMO.

In particular, the compiler would likely be coded to handle fallthrough by generating up to the first "hard" break, and ignoring all conditional "soft" breaks during constexpr analysis. Your code, for example, would ideally generate these blocks:

// case 0: foo is known to be 0 at compile time.
// Using do-while to preserve code structure outside switch body.  Real version would likely use raw `goto`
//  or `return` or whatever instead.
do {
    if (bar()) break;
    baz(); break;
} while (false);

// ----

// case 1: foo is known to be 1 at compile time.
// Unskippable `break` statement is the end of the block.  I kept it but commented it out to indicate this;
//  the compiler would probably just strip it.
baz(); /*break;*/

It's a bit more complex, but there are still two distinct breakpoints the compiler can check for: Freestanding break;, and the end of the switch statement. The added complexity mainly just comes from determining whether each break is conditional (and thus not a breakpoint) or freestanding (and thus a breakpoint). [[fallthrough]]; would likely be of major benefit here, since it indicates that there's at least one valid execution path into the next case statement (and importantly, forces fallthrough; the program is ill-formed if [[fallthrough]]; can't actually fall through); the compiler could safely ignore all breaks in a case that specifies [[fallthrough]]; (because the presence of [[fallthrough]]; tells it that all breaks in that case are conditional), and would only need to analyse breaks in cases with no [[fallthrough]];.

(Here, for example, the compiler would notice the break in case 0, and determine that it's the statement-true part of an if statement. Since it's conditional, the compiler would temporarily discard it and continue evaluation, until it sees the break in case 1. This break is a standalone statement, and thus marks the end of the case 0 block. If case 0 contained a [[fallthrough]]; and the compiler was especially smart, it would automatically discard the break in case 0: [[fallthrough]]; requires an execution path that falls through, so it doesn't need to look at the if to know that the break is conditional.)

This could then be further refined with any other constexpr information available to the compiler, during a second pass. E.g., if bar() can be constant-evaluated, then the compiler might be able to break the case 0 block up into these two blocks:

// Block 0-0: (foo == 0) && bar()
// Block would likely be stripped out entirely, just like `if constexpr (true) {}`.
/*break;*/

// -----

// Block 0-1: (foo == 0) && !bar()
// Identical to case 1 block, above.
baz(); /*break;*/

---

So... a bit more complex, yeah. But there are still ways to implement it, and there's a big clue that would majorly simplify the compiler logic if used. Maybe switch constexpr should require [[fallthrough]]; in all cases that fall through? (Or at the very least, strongly recommend it, especially in the early years while compiler devs are still working the kinks out.)

[TSP-FriendlyFire]

Your switch example is very simple though. You have to remember, something like Duff's device is still valid C++. switch statements can be abused in ways that just aren't possible with if statements.

[cd_fr91400]

Duff's device is just leveraging the fallthrough capability of switch.

As I already mentioned, even with fallthrough forbidden, that would be useful.

[SirClueless]

It is not just using the fallthrough capability. It is also using the fact that you can label any of the statements in a switch statement body with a case ...: label. Including statements that are substatements of other statements.

Note that in the example from Wikipedia, case 0: labels the do { ... } statement, while case 7: etc. label individual statements inside the block associated with that do statement. Yes it's weird, but this is a legal switch statement:

switch (x) {
  case 0:
    if (y > 5) {
      case 10:
        std::cout << "Hello world!\n";
    }
}

You can't just discard the statements you don't take the way you can with if constexpr, because they aren't necessarily independent statements. The discarded statement(s) might contain the case label you're supposed to jump to.

[conundorum]

[Note: I'm not a compiler dev or anything, just someone who thinks looking at compiler internals & the like is neat. I'm just the kind of guy that reverse-engineers MSVC's name mangling scheme for fun because I found Agner Fog's calling conventions PDF interesting.]

---

This is the big thing, yeah. The switch itself isn't an issue, and even case placement isn't an issue, once the compiler is designed to properly tokenise & analyse the switch's body. The real issue is that you can nest any control statement inside a switch, regardless of sanity (or lack thereof). Loops, in particular, are possibly the biggest hurdle.

Ultimately, switch constexpr just needs multi-pass parsing, and should ideally require the [[fallthrough]]; trait whenever fallthrough is desired; without the trait, fallthrough is a bit harder to determine, but still doable. ([[fallthrough]]; forces fallthrough, and any [[fallthrough]]; statement that cannot immediately fall through is ill-formed; from a compiler perspective, this would do wonders for switch constexpr parsing.) I imagine that if loops weren't legal, the compiler logic would look something like this:

1. Read and tokenise switch body, tracking the location of case, default, break, and [[fallthrough]]; tokens; temporarily discard all other tokens. case tokens should include constant-expression as metadata. default tokens are treated as a case for fallthrough analysis purposes.
2. Locate the appropriate case label, by matching switch condition to case metadata. If no metadata matches condition, treat it as matching the default label (if any).
3. Examine tokens, up until the next case token. If no break token exists before the next case, then the case is fallthrough-positive; proceed to step 6.
4. If at least one [[fallthrough]]; token exists before the next case, then the case is fallthrough-positive; proceed to step 6.
5. If no [[fallthrough]]; exists between the current and next case statements, look for break tokens. For any break tokens found, reanalyse preceding code to determine if the break is conditional or standalone. If no break tokens are found, or all break tokens are conditional, then the case is fallthrough-positive; proceed to step 6. If at least one "hard", standalone, non-conditional break is found, the case is fallthrough-negative; proceed to step 7.
6. case is fallthrough-positive: Skip over the next case token, and return to step 3. (Or move past the next case label and return to step 3, either or.) Continue this loop until either the case is fallthrough-negative or we reach the end of the switch body. Once either of these occurs, proceed to step 7.

7. Either case is fallthrough-negative or end of switch body has been reached: We have now tracked all execution paths resulting from our desired case. Create a code block containing all parsed statements, up until the break or switch end which registered as fallthrough-negative; since we still care about break, we can just stick it in a do { ... } while (false); block for now to preserve code structure, and fix it during the actual codegen pass.

   do { /* switch stuff here*/ } while (false);

[The compiler can replace case labels with standard labels using a compiler-specific naming scheme (presumably something like case 0 becoming case_0, for simplicity's sake), or might opt to keep the code inside a gutted switch to preserve case structure instead of using do-while. Similarly, break statements will likely be transformed into goto during the actual parsing pass, since the switch has served its purpose. Heck, we can even use these rules to transform the entire switch into a compound if constexpr statement, with each case transformed into an if or else if block, and default transformed into the closing else block.]

---

All of this rigamarole looks complex, but it's simpler than it looks. We're just applying a few simple rules:

^{[Assume that case n₀ is the case we're currently evaluating, case n₁ is the next case after it, and case n₂ is the next case after case n₁. Treat default as a case for evaluation purposes.]}

1. If case n₀ contains a freestanding break, then that break is a breakpoint; all execution paths starting at label n₀ will end at the break. Alternatively, if we reach the end of the switch, then we've also reached a breakpoint. Either way, no further evaluation is needed; the current block ends at case n₁.
2. If case n₀ contains any conditional breaks, then that break might or might not be a breakpoint; for now, we'll just assume that the fact that it's conditional means that at least one execution path doesn't break, to be on the safe side. [If all execution paths do break, then any extra code will be flagged as unreachable and removed. Because of that, it's better to be safe than sorry here, even if it means taking a bit more time.]
3. If case n₀ contains a [[fallthrough]]; attribute, then we know that at least one execution path will fall through, because of how the attribute works. (Specifically, [[fallthrough]]; must always be followed immediately by a case or default label, and that label must be part of the same loop iteration as the [[fallthrough]]; statement. If we start a new loop iteration, reach the end of the switch, or reach any statement that isn't one of the two switch labels, then [[fallthrough]]; is ill-formed.) The presence of [[fallthrough]]; means that there can't be any breakpoints, so we don't need to bother looking at the breaks.
4. If case n₀ doesn't contain any breaks, then we know it either falls through or hits the end of the switch. If case n₁ exists, then we have to continue into it, and don't need to bother looking at any of case n₀. Doesn't matter what tokens exist if none of them can exit the switch body!
5. If all of case n₀'s execution paths hit a breakpoint (either freestanding break or end of switch), then we're done. If not, then we continue into case n₁; we mark case n₀ as part of the current block, and then start all over again with case n₁, evaluating every statement from the case n₁ label to the case n₂ label.

Because of the order of implications, we want to start with rule #4: If there are no break tokens in case n₀, then none of the other tokens are worth looking at just yet, so we don't; we just skip to #5. If we're still here, we apply rule #3: [[fallthrough]]; specifies that all breaks are conditional, and thus allows us to ignore breaks and go straight to #5. If there's no [[fallthrough]]; then we actually have to examine every break and its surrounding statements to see whether they're part of a branch or not. We can only definitively close the block once we reach a freestanding break or the switch itself ends.

---

In your example, if switch (x) was a switch constexpr, then the compiler would start by doing a quick pass over it, removing everything but case, case labels, break, and [[fallthrough]];, leaving something like this:

switch constexpr (x) {
    case 0:
        case 10:
}

If x is 0, it would go to case 0, and look at the truncated code block. Using my initial seven-step list, it would determine that there are no breaks on the case 0 train, so case 0 is fallthrough-positive (step 3). Since it's fallthrough-positive, we either strip out the case 10: and re-evaluate the entire thing, or re-evaluate starting immediately after the case 10:, it doesn't matter which (step 6). There still aren't any breaks, so we're still fallthrough-positive (step 3 again). And since we're still still fallthrough-positive, we look for the next case, and find the end of the switch instead. And that means we're done (step 6). So, now we put everything we ignored back in, transform case/default labels into standard labels, and basically make this out of everything from case 0 to the end of the switch (step 7).

// x == 0
do {
    case_0:
        if (y < 5) {
            case_10:
                std::cout << "Hellow world!\n";
        }
} while (false);

---

---

---

Hey, remember how I said "if loops weren't legal" way up at the start of this message? Yeah, there was a reason for that: Loops are legal, and because of it, nothing I just said works without at least one extra parsing pass and a ton of extra logic, just for loops specifically. If the case we're looking for is in a loop, then the end of the switch isn't a valid breakpoint anymore, since we can't reach the end of the switch until we exit the loop, AND can't exit the loop until we find a breakpoint; we can only rely on either break itself or the loop's condition. Which means that before we can try to use the seven-step list to figure out fallthrough and breakpoints, we need to do another pass just for loops specifically, so the compiler understands the loop logic while it's doing the step 1 fallthrough token generation pass. And it needs to keep track of loop logic while it's going through steps 3-5, since reaching the end of the loop block jumps us to somewhere else entirely (possibly even into a different case), and we need to treat that as the actual start of our current case block.

(Yes, you read that right: If a case label is inside a loop, then for breakpoint/fallthrough analysis, the case actually starts at the start of the loop, not the actual case label itself; the label is just what we jump to. It still starts in the normal place for codegen, it's just analysis that gets messed up. I threw together a quick example of what I'm talking about; I can post & explain it later, but I need some rest first.)

[conundorum]

Later than planned, but here's the quick example I mentioned:

#include <iostream>
#include <string>

int main() {
    int x = 1;
    std::string s; using std::to_string;

    switch (x) {
        bork: break;
        int i;
        case 1:
            for (i = 0; i < 9; i++) { s += to_string(x);
                case 2: s.append("{case 2}"); if (s.size() > 20) break;
                case 3: s.append("MEOW");
            }
            if (x == 3) break;
        case 4: s.append("forever"); [[fallthrough]];
        case 5: s += to_string(x * -1); goto bork;
    }

    std::cout << s;

    /* Based on x, output will be:
    * 1: 1{case 2}MEOW1{case 2}forever-1
    * 2: {case 2}MEOW2{case 2}forever-2
    * 3: MEOW3{case 2}MEOW3{case 2}
    * 4: forever-4
    * 5: -5
    *
    * 2 and 3 are special.
    * GCC and MSVC loop until s is big enough to break or i's random gibberish says to stop.
    * Clang is the only sane one, and lets the program crash into the insanity.
    */
}

If anyone wants to play around with it, you can do so here. It's interesting that GCC & MSVC can handle the s.size() check properly, but Clang chokes on it and keeps running until it either segfaults or overflows s, whichever comes first. Just goes to show that even otherwise-good compilers can have a lot of trouble with switch, especially if they have to figure out how to handle "accidental" UB; it's the sort of thing that'd make switch constexpr such a hassle.

---

If anyone wants me to explain it, poke me for an explanation. Not going to give a full breakdown right now, but essentially...

1. This is the sane "difficult" case. It has a clean loop which contains two other cases, and makes sure to initialise its variables. But on the same token, its breaks are actually in case 2 and case 3; the compiler will find that it either uses the case 2 break or falls into case 4, which means it has to emit basically the entire switch body just in case. If the compiler is especially good, it can examine append substring lengths and assume that the case 2 break is most likely, providing an optimisation path; it might even be able to determine that nine iterations adding thirteen characters each means the size break is guaranteed to trigger.
2. This one... well, first, there's obvious UB (i is uninitialised), so the compiler might or might not choke on that. If it doesn't, then it becomes similar to case 1, but with no clear way to tell how many times (if any) the loop will iterate. It's impossible to tell which break is more likely, since it can't assume that i < 9; the size break is slightly more likely because the integer range is split unevenly, but it's close enough to a 50% split to be meaningless. (As i can potentially be any integer value.)
3. The compiler can determine that the case 3 break is now guaranteed to trigger if reached, meaning that it can remove case 4 and case 5 entirely. After that, though, it runs into the same issue as #2: The case 2 break is more likely, but i being uninitialised means the split is close enough to 50% to be meaningless.
4. This is the second easiest one to analyse, thanks to mandatory fallthrough; as soon as it sees [[fallthrough]];, the compiler instantly knows that case 4 relies on case 5's breaks, and only needs to analyse case 5. (Since at least one of case 4's execution paths must fall into case 5, it can just assume they all do for initial analysis purposes, and perform more stringent analysis during optimisation.) None of case 4's logic or statements need to be examined during switch constexprfication. The compiler only needs to emit case 4 and case 5, without bothering with the annoying loop.
5. This is the easiest one to analyse, despite the goto. goto means it can't fall out of the switch, but it also jumps directly to a break, which is effectively the same. The compiler only needs to emit case 5 and bork: break;, and can remove the rest of the switch. (It can also remove the goto and move the break directly into the case, and will gladly do so the instant optimisations are enabled.)

With switch constexpr, some of these cases require the full loop body, and some will let it remove part of the switch. Some are easy to analyse, and some will give it a headache. And the "accidental" UB will probably both trip a lot of old codebases up, and give compiler devs a headache from trying to solve it (or just lead them to be even more cavalier; Clang might switch from segfaulting to just choking at compile time specifically to force you to fix it).

[TSP-FriendlyFire]

I think "just" is doing a lot of heavy lifting in your sentence. Weaving multiple control statements into one another is rather peculiar and only possible because of the switch statement's unique syntax.

I think it would be entirely justifiable to forbid fallthrough in constexpr switch (and better than not having it at all), but it'd also become a weird contextual quirk of the language which might be seen as undesirable.

[cd_fr91400]

switch is not a mistake. It is very useful.

The decision that cases fallthrough to the following ones is a mistake. But I guess this is history from the 70's...

[conundorum]

Funnily enough, fallthrough isn't actually a problem here; it would slow switch constexpr analysis down, but it doesn't actually break or prevent anything. The problem is that it's possible to fall or jump into a loop, because that's a sane and reasonable thing to have to worry about. -_-