introduce `reachable` keyword for branch hints

[andrewrk]

Loosely inspired by #489 (comment) and #20642 (comment).

This proposal supplants:

• @expect() hint to optimizer #489
• replace @setCold with @cold #5177
• introduce @branchWeight builtin with numerical branch weights #20642

Introduces a new keyword, reachable, which takes an optional block label, just like break and continue.

Combined, these changes allow branches to hint about how likely or unlikely they are to be reached from any given location.

Basic example syntax:

if (x > 100) {
    reachable .likely;
    // ...
} else {
    // ...
}

Advanced example syntax (combined with #8220):

a: switch (x) {
    0 => b: {
        reachable :a .likely;
        continue :a 1;
    },
    1 => {
        reachable :a .unlikely;
        reachable :b .likely;
        // ...
    },
    // ...
}

pub const BranchHint = enum {
    /// This branch of control flow is more likely to be reached than its peers.
    /// The optimizer should optimize for reaching it.
    likely,
    /// Equivalent to no hint given. Compile error to use this value literally.
    baseline,
    /// This branch of control flow is less likely to be reached than its peers.
    /// The optimizer should optimize for not reaching it.
    unlikely,
    /// This branch of control flow is unlikely to *ever* be reached.
    /// The optimizer may place it in a different page of memory to optimize other branches.
    cold,
    /// For unlabeled `reachable` this is equivalent to the `unreachable`
    /// keyword and thus a compile error to use this value literally because `unreachable` must be
    /// used instead.
    never,
    /// It is difficult to predict whether this branch of control flow will be reached.
    /// The optimizer should avoid branching behavior with expensive mispredictions.
    unpredictable,
};

Some rules:

• The BranchHint value is a comptime expression.
• For comparison purposes, "likely" compares greater than than "baseline" (default unannotated branch weight), which compares greater than "unlikely". Equal weight branches are allowed.
• All branches that lead to a @panic (including from safety check) implicitly are "cold".
• It is safety-checked illegal behavior to jump to a branch with a "never reachable" hint with a label corresponding to the jumped-from block.
• Multiple reachable statements for the same (or no) label is a compile error.
• Just like how unreachable is required to terminate a block, all reachable statements are required to be at the beginning of a block.

Furthermore:

• No "expect" builtin or similar.
• No @cold or @setCold builtin. (replaced by reachable .cold; at the beginning of the function.
• Error branches (weight error branches against errors #84) get a default hint of unlikely and can be overridden with this reachable keyword.

Compared to the existing proposals, this generalizes better to switch expressions, and it actually addresses labeled continue syntax inside switch expressions, as well as loops in general.

I will make a separate followup proposal for annotating source with PGO data.

Alternate syntax idea: comefrom 😜

[RetroDev256]

I really like this proposal. If this is accepted, would we really need an unreachable keyword? I can imagine reachable .never; serving this purpose perfectly. Not sure if it would complicate the compiler though.

[rohlem]

EDIT: syntax issue in advanced example

There's a slight syntax issue in the "advanced example" given - in status quo block labels are only available within that block.
switch prong 1 isn't within block b, so it cannot refer to :b in status-quo.

Label visibility could be special-cased within switch statements and their prongs.
I think the only truly consistent solution would be to make labels globally visible inside function scope.
That idea actually sounds pretty annoying to me, but maybe it wouldn't be so bad in practice.

Alternatively, because only reachable ever has to refer to outside blocks,
we could special-case the label lookup for reachable to the whole function scope - and compile error if that label isn't unique.
That would be ideal imo.

---

question about limiting `reachable` to the beginning of blocks

all reachable statements are required to be at the beginning of a block.

Does this talk about syntactic blocks {...}, or blocks in the sense of branching / control flow?
I think reachable statements after a branch (to apply to the rest of the block) can make sense:

a: switch(x) {
  else => {
    if (y) continue :a 4;
    reachable :a .unlikely;
    // rest of the block - could still reach :a, but unlikely
    if (z) continue :a 33;
    reachable .unlikely; //it's likely we have branched away at this point
  },
}

Otherwise you would be forced to introduce a new block, and increase indentation,
just so the reachable statements become valid again, even though there's no semantic difference.

---

questions about the behavior in loops and with branching backward

To me it looks like there's an important distinction between the two forms:

• reachable without label seems to apply to whether the block will generally be entered from the outside.
• reachable :label seems to apply to whether the block will be (re-)entered from this point on.

If that distinction is correct, then there may be an esoteric edge-case where both unlabeled reachable and labeled reachable to a block within that same block could be technically correct:

while(iterator.next()) |element| {
  if (at_most_once) a: {
    reachable .likely; //it's likely this block is reached once,
    reachable :a .never; //but once it has been entered we ensure/assert we won't re-enter it.
  };
  // rest of the loop with many other ways to exit it
}

This information could only ever be utilized when transforming/unrolling the loop.
This now makes me wonder though what behavior should be formalized when looping back to an earlier point:

xs: switch(@as(u8, 0)) {
  0 => x0: {
    if (skip_x1_x2()) continue :xs 3;
    continue :xs 1;
  },
  1 => x1: {
    if (skip_x2()) continue :xs 3;
    continue :xs 2;
  },
  2 => x2: {
    reachable :x1 .never; //This essentially asserts x1 is never reached again, right?
    continue :xs 3;
  },
  3 => x3: {
    if (cond) continue :xs 0; //Is x1 still never-reachable again from here? Or only if we didn't skip x2?
  },
}

I think the sanest behavior would be to effectively "undo" the (labeled) reachable statements encountered in between.
Imo this best maps to the expectation that reachable is an annotation for code layout, and code layout won't change when looping back to an earlier point (unless the compiler inlined this branching).
I think the simplest way to phrase this would be that reachable influences the optimization of

• backward branching targets (direct jumps using continue) and
• reachable code paths going forward (without using continue),
• but does not apply to reachable code paths after backward branching.

---

@RetroDev256 In status-quo unreachable is an expression of type noreturn, f.e. in catch unreachable,
while the newly introduced reachable seems only valid as a statement.
We could replace pure unreachable; statements with reachable .never;,
but status-quo is shorter and easier/quicker to read, so I personally don't think we should.
(Plus the original post currently states the opposite - keep unreachable; and declare reachable .never; invalid because noncanonical.)

[Rexicon226]

It's unclear why this needs to be a keyword over a builtin other than accepting labeled blocks for switch/continue. Even then, labeled usage has edge cases:

• What does it mean when two cases from switch blocks are unlikely?

a: switch (x) {
    0 => b: {
        reachable :a .unlikely;
    },
    1 => c: {
        reachable :a .unlikely;
    },
    2 => d: {
        reachable :a .unlikely;
    },
}

• What does it mean when two cases are likely from case block with continue?

// 2
a: switch (x) {
    0 => b: {
        continue :a f();
    },
    1 => c: {
        reachable :b .likely;
    },
    2 => d: {
        reachable :b .likely;
    },
}

Switch statements have unpredictable codegen order, especially since codegen doesn't look at the order of cases. likely/unlikely would make sense if Zig had an order as it influences fallthrough.

[andrewrk]

It's unclear why this needs to be a keyword over a builtin other than accepting labeled blocks for switch/continue.

There are no builtins that accept a branch label as a parameter, so the alternative would be novel syntax. On the other hand, there is already a keyword that accepts a possibly labeled expression. This is simpler to specify & implement as well as easier for people to learn & remember.

What does it mean when two cases from switch blocks are unlikely?
What does it mean when two cases are likely from case block with continue?

These questions are answered by this part of the proposal:

For comparison purposes, "likely" compares greater than than "baseline" (default unannotated branch weight), which compares greater than "unlikely". Equal weight branches are allowed.

Switch statements have unpredictable codegen order, especially since codegen doesn't look at the order of cases. likely/unlikely would make sense if Zig had an order as it influences fallthrough.

I'm not sure what point you are trying to make here. Switch expressions have codegen order dictated by the same lowering rules of all code: emit the best machine code possible, given the optimization mode and other compiler flags, obeying all language rules, exploiting available hints. The absence of a language rule (switch expression prong codegen order) provides flexibility in the search space of these goals.

I think the thing you're missing (as pointed out by @mlugg in #20642 (comment)) is that this information, while syntactically convenient to reside in the destination blocks of branches, is actually data belonging to the source location of the branch. Other proposed solutions to this problem fail to model this accurately.

[mlugg]

This proposal seems very flawed to me. Specifically, the block labeling feature doesn't seem well-thought-out (and of course, without that, this could just be a builtin). I have two issues with it.

The example you give of using this with labeled blocks ("Advanced example syntax") doesn't actually give the compiler particularly useful information: we can tell it that it is likely to loop into the labeled switch again, but we can't communicate which prong we are likely to reach, which may be desirable information. So, this proposal fails to provide all the information which an optimizer could utilize about branch reachability. I don't think it's worth introducing a new keyword for a sub-optimal feature like this.

Actually, your example makes reference to a block b outside of that block's scope. I can't tell whether that was intentional -- it'd be helpful if you could elaborate on the examples, as they don't make much sense to me as-is. Allowing this would fix the problem I mentioned above, but as @rohlem mentions, it breaks the existing rules around block scoping. For break and continue, the block label can only refer to a syntactically enclosing block; here, you are referring to the label of a "sibling". The only reasonable way I can see to achieve this is to "bless" the form ... => foo: { ... } to be a specifically recognised syntax form which makes foo visible to sibling blocks for reachable. This complicates the language's syntactic rules, and makes the block references incredibly non-obvious.

The second problem I have with this syntax is that the meaning of reachable is incredibly different depending on whether a label is given. For constructs like break and continue, omitting a label basically says "infer the block/loop this applies to" -- you could always have added a label and gotten the same behavior. This is not true of reachable. A plain reachable .likely means "this block is likely to be reached from preceding code paths", while (AFAICT) reachable :blk .likely means "starting from this block, it is likely to reach blk". That's a glaring inconsistency in the meaning of the builtin -- in essence, the unlabeled form gives hints about how we got here, while the labeled form gives hints about where we will go from here. Those are two different things.

[rohlem]

Only now I realized that there's technically the reading of reachable :a l meaning "current block is reachable from label a with likelihood l".

I think for me the logical ordering of the full phrase would be (target) is reachable from (source) with likelihood l.
With that phrasing, proposed reachable l means "@thisBlock() is reachable from @implicitEntriesToThisBlock() with likelihood l",
and proposed reachable :a l means "label a is reachable from @thisBlock() with likelihood l".

I don't know whether the syntax should allow this additional complexity - probably not -,
but to me this more explicit form better shows the complexity and difference in semantics already present.
Fwiw, I think the ordering :a reachable .likely; would be a bit more intuitive and just as readable. Just an idea though.

[andrewrk]

Only now I realized that there's technically the reading of reachable :a l meaning "current block is reachable from label a with likelihood l".

Right that's the idea. I think @mlugg missed this nuance too.

[nektro]

ohhh i definitely missed that as well in my first readings with the current naming. but that does make more sense given the proposals this was meant to replace.

[mlugg]

Hm, okay, I see. I will say, I think the fact that 3 people individually misunderstood the intention here in exactly the same way indicates that this syntax is unclear. But, ignoring that, let me discuss the proposal as intended.

I feel like the example given here overloads the meaning of the switch label a little. The labeled continue is, very loosely, meant to mean "go back up to the switch but replacing the operand with this value". Yes, that's not the lowering, but it's the approximate mental model. Meanwhile, reachable :a .likely refers only to the initial dispatch of the switch. If anything, I would expect the switch statement to be in some entry: { ... } block, and the annotation to say reachable :entry .likely; i.e. the given label has to refer to a block.

To me, the block scoping issue still makes this proposal feel inappropriate. There is no solution to this problem which retains parity with other parts of the language, and even ignoring that, allowing these out-of-scope block references just feels, frankly, very messy. We could define rules to avoid block labels "leaking" into surrounding scopes too much, but every change you make there just makes the language more confusing and the spec more complex.

I feel that this proposal overgeneralizes the problem and maybe gives it higher status than it deserves. Branch hint information is generally not that valuable to the compiler, since there are no actual branch hint instructions on most architectures and the heavy lifting is done by the runtime branch predictor. Moreover, the actually useful information depends on the type of branching construct and therefore generalizes poorly:

1. If-Else

Here, the compiler's options are mostly limited to which branch it lays out first and which second. By default, it would leave the cases as is, so the useful information is whether the condition is unlikely. If it is known to be unpredictable, the compiler might try to lower to predicate instructions, but this tends to be faster only for really tiny IFs.

2. Loops

There is relatively little that the compiler can do about the control flow structure of a loop per se. But it may be interested in whether the loop is hot, so it can invest into unrolling, vectorizing, and other bloaty optimizations. This annotation may also take the average number of iterations from PGO instead. This is technically not a branch hint at all.

3. Functions

If a function is known to be cold, it can be relocated to another segment. I'm not sure this is useful in other contexts though. Do compilers really relocate IF branches and switch cases? A hot annotation may be beneficial for the same reasons as in loops.

4. Switches

This is actually the most interesting case, as relative branch weights can really help the compiler select optimal fast paths in comparison-based switches. For switches that are compiled to a computed goto, this is probably less relevant.

5. Comefrom

This is the goto switch case, but it's not clear to me why it's important to know where a given case is likely to be reached from. Maybe so you can reduce long branches in really big-ass switches? But this is really a micro-optimization and the corresponding constrained layout problem might be computationally expensive. I really think there should be some empirical evidence that this is worthwhile, before bringing this information into the language.

TL;DR

Even though having a bunch of separate builtins with optional PGO parameters is less elegant, it probably gives more precise information where it can actually be useful, will hopefully discourage overuse (in my experience it's really quite hard to outwit the compiler on this front), and does not require keywords and non-standard block label semantics.