Standard annotations for expected code path to optimize

[ChrisDodd]

There should be a way for the programmer to indicate which path through a control or parser should be the most common and should be optimized for.

One possibility would be something like:

if (pred) @unexpected {
    ... code that rearely executes
}

putting an @unexpected annotation on the block in the if statement tells optimizers that the code in the block will rarely be executed and the fall-through case should be optimized for.

Putting the annotation on the statement fits well with what p4c currently supports (annotations on block statements) and also works in other cases like:

switch(something) {
    case 1: @expected {
        ... common case code ...
    }
    case 2: {
        ... another case, less common ...
    }
    default: @unexpected {
        ... rarely executed code ...
    }
}

This contrasts with eg. gccc's way of doing this sort of thing, which is by having a __builtin_expected(expression, value) function.

[vlstill]

I like the syntax more than the GCC one. It is also very similar (taking into account the different syntax for annotations/attributes) to the C++20 way of doing the same, the [[likely]]/[[unlikely]] attribute (although that one technically applies to labels, not the blocks, but the effect is very similar). I would slightly prefer the C++ naming of these ("likely"/"unlikely") as "unexpected" can sound more like something that "should not happen" rather than something that is "unlikely/rare to happen".

Presumably, this would have very little impact on the rest of the spec as it would only say these are recommendations the compiler might take into account, right?

How does this apply to select? Would we need to allow annotations on the select cases, or are they already there (unlike switch/if cases these are not blocks, just names)?

[ChrisDodd]

The grammar (in p4c and the spec) currently does not allow annotations on select cases -- that should probably be fixed.

@likely/@unlikely as annotations seems fine to me. The precise naming should be added to the "reserved/predefined" annotations in appendix C of the spec

[mihaibudiu]

The most unpleasant part may be to make sure the annotations are not lost by any optimization.
If they are on a block, the block cannot be removed, and no optimization can cross the block boundaries.

[vlstill]

The most unpleasant part may be to make sure the annotations are not lost by any optimization.

Or just any transformation, e.g. just wrapping a block in a new one will probably remove or deactivate the annotation unless it is handled somehow. I presume if (foo) { @likely { block }} does not really work -- which might lead to unexpected results. P4C should probably at least warn on uses of these annotations in palaces where they don't make sense (but that might be tricky, as it would be somewhat target dependent).

If they are on a block, the block cannot be removed, and no optimization can cross the block boundaries.

I think it would make sense for these annotations to not hamper other optimizations. So things like hoisting common code out of then and else branch should absolutely be OK, even if one of the branches is @(un)likely.

[vlstill]

An alternative would be to put annotations on switch and select cases and somehow attach an annotation to if which says that the IF is likely to go to then or else branch -- this way, we would avoid putting them on block statements and therefore preserving them would be presumably easier.

[mihaibudiu]

most passes don't know anything about annotations, so they try to leave the code involving them untouched.
probably this may require reviewing lots of passes

[ChrisDodd]

In general, passes should preserve annotations on blocks, which inhibits some cases where blocks could be combined.

In my PR I fixed a number of cases where annotations were inadvertently being deleted from blocks when those blocks were being moved from one place to another, and extended the code to collapse blocks to allow collapsing blocks when they have the same annotation (things like @likely ( @likely ( ... ) ... ) -- in practice that would never happen with @likely but does happen with compiler-inserted @hidden annotations).

[vlstill]

I'd just like to highlight this, as it was not addressed (#1308 (comment)):

How does this apply to select? Would we need to allow annotations on the select cases, or are they already there (unlike switch/if cases these are not blocks, just names)?

Since select right-hand-side cannot be a block but just name, how do we add likely/unlikely there?

[asl]

In general, passes should preserve annotations on blocks, which inhibits some cases where blocks could be combined.

Still, this looks a bit fragile. But I guess there is no currently a way to enforce this (e.g. to check if an annotation is lost or preserved). Fortunately these are just optimization hints, but what if annotation would be required for correctness?

Having an extern (similar to gcc's __builtin_expect) on the other hand would potentially inhibit some optimizations...

[ChrisDodd]

Having an extern (similar to gcc's __builtin_expect) on the other hand would potentially inhibit some optimizations...

Having an extern means that backends that don't care will need to explicitly look for and skip/remove the extern. Annotations are generally ignored by backends by default, so no changes are needed.

[jafingerhut]

In general, passes should preserve annotations on blocks, which inhibits some cases where blocks could be combined.

Still, this looks a bit fragile. But I guess there is no currently a way to enforce this (e.g. to check if an annotation is lost or preserved). Fortunately these are just optimization hints, but what if annotation would be required for correctness?

The best way to enforce this are the usual ways:

• Developers being vigilant during code review, and making code changes, that preserving annotations is important.
• Having a suite of tests that checks whether annotations are lost or preserved, and fail if they are lost.

We currently have many tests that check whether the output of the frontend and midend compiler passes, when used to generate P4 code from them, are identical to expected file contents in the p4c repo, in the testdata/*_outputs/ directories. Is that a sufficient way to have a test that determines whether annotations have been lost or preserved?