Reduce type checking overhead

[asl]

After refmap changes in frontend, TypeInference is the pass that is called most often. It can operate in two modes:

• read-write, where casts are inserted as necessary
• read-only that just performs typechecking (and fills type map)

For one downstream case I noticed that it was invoked 76 times on the top level and only few of those are read-write. Each of these sweeps over the input could take up to ~300 ms, meaning that we are spending ~20 seconds a total just for type checking. Given that overall compilation time is ~70 seconds, the typechecking time is quite large. In addition to this type checking is run on a subtree during each method call resolution, etc.

While it is possible to adorn expressions with inferred types, the passes are not yet prepared for this and require a TypeMap to operate.

One possible way to improve the things is to make type checking (read-only type inference) a proper Inspector. Despite the name, type checking is still a Transform, so it clones the whole IR just to drop the result as nothing was changed. This causes big malloc traffic, increased garbage collection pressure, plus Transform logic is more complex that of Inspector.

This would require some refactoring to allow code reuse between Transform and Inspector modes.

Experiments show that we can expect improvements within 5-10% range from frontend / midend time.

[asl]

Tagging @ChrisDodd

[vlstill]

While it is possible to adorn expressions with inferred types, the passes are not yet prepared for this and require a TypeMap to operate.

I am wondering if we should say that from some point in the compilation (ideally from the initial type-check, but later may be needed) the types in the ->type attribute should be there and correct. Then we could start rewriting passes to actually make use of it and drop dependency on type map.

I believe most passes don't actually need TypeMap if they can count on ->type being correct.

• Primitive types can always be fully resolved using ->type.
• Struct and type names in general (IR::Type_Name) can be resolved using ->type + a reference resolver (either ReferenceMap, or ResolutionContext if the IR::Type_Name is being resolved in the visitor context it exists it.

There are some other features of TypeMap that I don't think have direct equivalent (getCanonical, getSubstitution, isCompileTimeConstant, isLeftValue). For the latter two (end especially the compile-time-constness), we might actually want to think about them a bit more, especially in connection to spec issues p4lang/p4-spec#1213, p4lang/p4-spec#1290, p4lang/p4-spec#1291. I wonder if we should actually make the constness part of the type system. Then there is widthBits which has quite a weird interface and should be easy to pull out as a freestanding function taking reference resolver.

This way we may need to occasionally run the read-only type checker to validate the ->type, but TypeInference should be rarely used. This would be a long and gradual project though (and some passes even count on TypeInference running after them to insert casts.

[ChrisDodd]

This was the original design -- once type inferencing runs, the ->type field on every expression should be set and should be correct (and should remain correct). One problem is that this really requires putting type specializations into to the IR rather than just in the type map, which makes dumping the IR trickier (but not impossible).

[vlstill]

One problem is that this really requires putting type specializations into to the IR rather than just in the type map, which makes dumping the IR trickier (but not impossible).

Don't we already use Type_Specialized for specializations?

[ChrisDodd]

There's also Type_SpecializedCanonical for the direct specialized type (referring to the base type directly rather than by name as with Type_Specialized which makes it more useful).