Create a new, smaller frontend

[vlstill]

Taking ideas from #4633 to an issue.

These changes are increasingly showing that the current frontend/midend split is not really working. Indeed even which frontend optiomizations disabled, it does actually a lot of optimizations and not really necessary rewriting (constant folding, parser-if elimination, control flow simplications). One path forward I could see would be to start definting a "minimal frontend" that would be basically responsible of checking validity of the program, including type checking but would not very little rewriting. It might be tricky to say where the limits should be (inserting casts explicitly is probably OK, expanding the ... default values likely too, but constant folding or removal of useless casts is not OK I'd say). SideEffectsOrdering is probably also outside of frontend. Then we could define the exiting frontend to start with these passes and the targets that want would switch to the new frontend and move all the optimizations they want to midend.

What could get tricky is that some midend passes may have implict preconditions that the current frontend (some pass from it) had already executed.

[vlstill]

In reply to @ChrisDodd, #4633 (comment):

These changes are increasingly showing that the current frontend/midend split is not really working. Indeed even which frontend optiomizations disabled, it does actually a lot of optimizations and not really necessary rewriting (constant folding, parser-if elimination, control flow simplications).

The genesis of this (doing "too much" in the frontend) is allowing bit<expr> where expr is any expression that can be reduced to a constant. We need that in order to do typechecking properly (which we want in the frontend), so we end up needing inlining (in case the expression calls some function), which in turn brings in lots of other requirements as well.

One possibility is that we set things up to do these passes that should not be in the frontend only in limited contexts (like type arguments) when running in the frontend, so as to allow proper typechecking, without doing everything that any target might not like. Then targets could run them (or not) in the midend as desired.

That is a good point, we want to make sure the program is type-checked in the minimal frontend.

The C++ compiler has a similar problem (constexpr values in template parameters or other compile-time contexts), I believe they solve it by interpreting the values in question. We might already have all the infrastructure for that in place as I believe P4testgen already does expression-level constant folding and other optimizations during the symbolic execution (on concrete values, not on symbolic once). Using that (efficiently) in the type checking might require significant refactor though but I am not able to say how much as I am not very familiar with the code. But it would make some things easier. I can even imagine some targets benefiting from not having to inline all the code into the base blocks.

To do this, we would need to understand well what needs to happen in frontend and what are requirements of these passes.

[fruffy]

The Petr4 paper claims the type-inference algorithm of P4C does not need to be as complicated as it currently is (Section 4 - Type Checker). One approach could be to write a clean and easily extendable type-inference/checking pass from scratch. Constant folding on bit<> and int<> types might be the only prerequisite.

This minimal front-end could be nice, then I could reimplement a translation-validation-style tool within the tools framework. Gauntlet, which uses its own type-inference implementation is too hard too maintain currently.

P4testgen already does expression-level constant folding and other optimizations during the symbolic execution (on concrete values, not on symbolic once)

Yes, we extended the ConstantFolding pass to be standalone without requiring a reference or type map. That also applies to StrengthReduction.

[ChrisDodd]

The problem comes when someone wants to do something like bit<(-x.minSizeInBits() % 8)> padding;

[vlstill]

The Petr4 paper claims the type-inference algorithm of P4C does not need to be as complicated as it currently is (Section 4 - Type Checker).

Thanks for pointing this out. I also wanted to take a look at p4lang/p4-spec#1213 which I believe tries to clear wording around compile-time values.

One approach could be to write a clean and easily extendable type-inference/checking pass from scratch. Constant folding on bit<> and int<> types might be the only prerequisite.

Could be. The downside of cource is we could end up with two typechecking passes with slightly different bugs. But I that could happen with any gradual approach too and we would probably be get worse code of the type checker that way. First we need to know where in the type system arbitrary expressions are allowed (is it just bit<>/int<>/varbit<>>?).

The problem comes when someone wants to do something like bit<(-x.minSizeInBits() % 8)> padding;

Sure, but if type of x is know, this is no problem. Can it even be generic? The parser/control declarations (not just type, i.e. with body) cannot be generic. This just imposes ordering on getting information from the source code, but this will already be covered by the general definition-use ordering. So we would just need to evaluate (= fold) the expression inside <...>.