[RFC] The Cost of Templates when Building Flang

Subprojects Flang
1

The time and/or memory requirements to build Flang are an often heard, not only by new users. Examples:

image

The number of compile Flang build jobs can limited with FLANG_PARALLEL_COMPILE_JOBS. However, it is off by default, only supported by Ninja, and users do not really want to limit parallelism.

The reason main reason is Flang’s reliance on templates. I identified two patterns that I think contributes to the majority of the unusual build cost:

  1. std::variant polymorphism: Instead of class inheritance such as
class Superclass { virtual void func(); };
class DerivedA : public Superclass {};
class DerivedB : public Superclass {};
obj->func();

Flang uses:

class DerivedA { void func(); } ;
class DerivedB { void func(); };
template<> 
class Superclass {
  UNION_CLASS_BOILERPLATE(Superclass)
  std::variant<DerivedA, DerivedB> u;
};
std::visit([](const auto &v) {
  v.func();
}, obj.u);

There are three big hierarchies built like that, each have slightly different design: the parse tree, the evaluate tree, and expressions/operations.

  1. Template arguments replacing immutable fields. Instead of what Clang does
class Expr : public ValueStmt {
 QualType TR; // Return type

Flang does:

template <typename DERIVED, typename RESULT, typename... OPERANDS>
class Operation;
...
template <TypeCategory CAT, int KIND> 
class Expr<Type<CAT,KIND>> { // Pseudocode, these are template specializations per CAT
  std::variant<...> u; // Possible operations/constants/... returning value of this CAT

That is, Operations (such as Subtract) are a CRTP[2] instantiated for each possible combination of result and operand types.
Expr are an object with a nested std::variant of possible operations (or constant), templated by the Type of the result.

Flang has 7 type categories each with a set of supported kinds (e.g. INTEGER supports the kinds 1, 2, 4, 8, 16 corresponding to the width in bytes), which makes in total 20 Types + dynamic ones. Fortunately only the conversion operation can have the result and operand types (FROM, TO) be chosen combinatorially and call arguments are modelled using dynamic types. That still means 20 instantiations for each expression supported by Flang. And most instantiated classes of a different KIND do exactly the same. One may think of it as storing the KIND as part of a function pointer, but without masking out the KIND part so we have a copy of the code for each of them.

I did some measurements compilation time using gcc and Clang, the latter with ClangBuildAnalyzer. This is a standalone build of Flang with ninja all, i.e. the LLVM/MLIR libraries and Clang are not part of the build. Also, I measured the compile time of the 3 Fortran-only applications in SPEC 2017 (603.bwaves_s, 649.fotonik3d_s, 654.roms_s), using the gcc-compiled flang. This runs on a 512 thread, 2+ TB RAM machine, but thread count is limited with -j128.

Baseline, Compiled with GCC 11.4, PCH disabled

Baseline, Compiled with Clang 23git, PCH disabled, ClangBuildAnalyzer

Baseline, Compiled with GCC 11.4, PCH enabled

Baseline, Compiled with Clang 23git, PCH enabled, ClangBuildAnalyzer

Baseline, SPEC CPU 2017 Fortran build time[3]

Key takeaways (maybe you find more interesting details):

  • Clang (132.6s) compiles a bit faster than gcc (164.7s) according to the wall clock, but consumed more user CPU time. This is due to the longest TU taking more time with GCC (160.2s vs 130.5s). That is, due to the massive parallelism available, compilation is dominated by the slowest TU build.
  • GCC requires a lot more memory (up to 8 GB RSS per TU) than Clang (4.2 GB)
  • lib/Semantics/check-omp-atomic.cpp is the most expensive TU. With Clang, lib/Lower/OpenMP/OpenMP.cpp requires the most memory.
  • With PCH enabled, gcc wall time is slower (due to longer critical path) and requires more (!) memory, but user time is 9% less user time
  • With PCH enabled, clang’s wall time is 5% slower, but uses 1/3rd less memory and 27% less user time. Compare to [flang] Use precompiled headers in Frontend, Lower, Parser, Semantics and Evaluate by mrkajetanp · Pull Request #131137 · llvm/llvm-project · GitHub
  • Template instantiation takes 37% of the CPU time (Clang, using patch adapted from ⚙ D36946 [time-report] Add Template Instantiation Timer). GCC’s -ftime-trace reports even 45%.
  • As expected, std::visit and std::variant by far dominate the template costs. Flang has its own visit implementation that claims to have less overhead, but seems to used a lot less often.
  • Flang performance is improved by -mllvm --mlir-disable-threading. On this system (512 logicial threads), MLIR multithreading increased wall time by 36%, User CPU time by 165%, and System CPU time by 30000%.

Lowest-Hanging Fruit: KIND template parameter

Removing template parameters has already been done on Flang-RT ([flang-rt] Rework findloc.cpp to dispatch target at runtime by jhuber6 · Pull Request #197756 · llvm/llvm-project · GitHub, [flang-rt] Rework findloc.cpp to dispatch target at runtime by jhuber6 · Pull Request #197756 · llvm/llvm-project · GitHub), including removing KIND and converting template parameters to function arguments or class members. Removing KIND would reduce the number of Expr/Type-related template instantiations from 20 to 7.

The code is available here: [Flang] KIND De-Templatization by Meinersbur · Pull Request #206907 · llvm/llvm-project · GitHub. This was mostly done by AI and not intended to land in this form. Despite being based on a 3 weeks old commit and touching most files, it does not have a merge conflict with main yet.

KIND template removal, Compiled with GCC 11.4, PCH disabled

KIND template removal, Compiled with Clang 23git, PCH disabled, ClangBuildAnalyzer

KIND template removal, Compiled with GCC 11.4, PCH enabled

KIND template removal, Compiled with Clang 23git, PCH enabled, ClangBuildAnalyzer

KIND template removal, SPEC CPU 2017 Fortran build time[3:1]

Key takeaways

  • GCC reduced to 89.5s (-46%) Wall time, 4938s (-31%) User CPU time, Up to 5.1 GB (-37%) MaxRSS per TU
  • Clang reduced to 86s (-35%) Wall time, 7692.9s (-35%) User CPU time, Up to 3.8 GB (-21%) MaxRSS per TU
  • 37% fewer std::visit template (std::__do_visit) instantiations
  • The most costly TUs now are lib/Parser/openmp-parsers.cpp, lib/Lower/OpenMP/OpenMP.cpp, lib/Semantics/check-omp-structure.cpp
  • Fortran build time changes are below noise level.

Conclusion/Opinion

IMHO de-templatization is worth the one-time churn of applying such a patch. The KIND template parameter was just the lowest-hanging fruit and already showed quite significant build time/memory improvements. I also think Flang should not need to maintain its own arbitrary-precision implementation for ints and floats when LLVM already has one. I generally find Flang’s style of auxiliary classes for sum types (e.g. InternalSubprogramPart) and product types (e.g. DeclarationConstruct) with meaningless member names such as u and t are hard to read and pose trouble with IDE support. The long build times make a edit-compile-debug cycle a churn. Long template error messages makes me rely on AI to fix it.

I would go even further an update Flang’s object model to follow closer what LLVM/Clang/MLIR is doing and push the compile memory usage below the 2GB limit:

  • Proper class hierarchies
  • Custom RTTI type ID that describe the underlying Parse/Evaluate tree node type like LLVM/Clang. Allows the use of llvm::cast<> instead of std::get<>
  • Interfaces either like LLVM faced (e.g. MemIntrinsic) or MLIR-style concepts[4]
  • Dispatches like std::visit should be only present in .cpp files. HMHO it’s a sign that an abstraction is missing.
  • Use of flang-tblgen to generate some of the class boilerplate instead of templates/preprocessor macros.
  • De-templatization allows moving more code into .cpp to be processed only once, instead of included into many TUs and object files.

  1. we must hate new users ↩︎

  2. Curiously Recurring Template Pattern ↩︎

  3. Measurement was taken several times, this was the minimal wall time. Using -mmlir --mlir-disable-threading to disable threading. ↩︎ ↩︎

  4. I think the MLIR concept interfaces are over-engineered; I’d prefer something that does not require specifying the interface in tblgen ↩︎

18 Likes
LLVM Weekly - #653, July 6th 2026
2

These are central to the parse-tree visitor. There are a few known kinds of AST nodes, the three most common are wrappers, tuples and unions. Wrappers have a single v member, tuples have t and unions have u. The visitor determines the kind based on the type trait associated with each of those and visits the expected member. This makes the parse-tree visitor invariant with respect to adding new AST nodes.

Edit: I think the biggest potential is in the evaluate::Expr classes. In my experience that is where most of the compilation time and memory usage is spent, plus its scope is much more limited than that of the AST.

3

IMHO it strange for a visitor pattern to force member names to be meaningless. More popular
approaches:

  1. Common base class/interface for “visitable” objects: clang::Stmt::children(), DynamicRecursiveASTVisitor
  2. CRTP dispatch: clang::DeclVisitor (not invariant though, but backed by a central DeclNodes.inc)
  3. Traits classes: llvm:DenseMapInfo, llvm::GraphTraits
4

There’s also the related slow compile of llvm/unittests/Frontend/OpenMPDecompositionTest.cpp, also due to variant+visit instantiations. I would highly appreciate if we could do something about this. For me, this is one of the slowest TU in LLVM and one of the reasons why I avoid building unittests. (For me personally, it would already suffice to move this out of llvm/ :wink: )

1 Like
5

Massive +1 to anything that tries to combat the insane flang resource requirements. I’ve done a lot of working trying to pull Fortran out of dependency paths just because of this. We should have enough runtime tests to confirm whether or not any blanket improvements are still functional.

1 Like
6

In today’s Flang biweekly call, the argument was made that the templates are to ensure correctness at compile-time. I will argue that templates are not the right tool for build-time verification.

  1. Results in machine-code output: A check comes with additional costs in form of redundant functions in the executable. E.g.

So this checks convertibility at compile-time. The cost is up to (minus the ones that are illegal by that static assert) 20 * 7 template instantiations of AsFortran and all members of `Operation. Fortunately the KIND is already omitted here, or it would be 20*20. That compile-time type check is directly visible in the flang binary. Identical COMDAT folding and inlining might reduce the effect though.

  1. Does not scale: You cannot check exhaustively, that would cause an exponential compile-time explosion. That’s why the function expression is NOT derived from Operation, even for builtins, but is a FunctionRef. Its operands are of type ActualArgument which is an Expr<SomeType>, which is a wrapper for a variant of an Expr of a concrete type, i.e. dynamic.

  2. Redundant to run-time checks: Source code it not known a compile-time. This has the consequence that the same compile-time check has to be implemented again for use at runtime. Some very clever SFINAE could maybe reuse the static_assert above, but in Flang it is done here: llvm-project/flang/lib/Evaluate/tools.cpp at 7b8c4f5ad69d8fabf4bb71494f748fa0d7c47774 · llvm/llvm-project · GitHub, among other places. So even if the compile-time check is correct, the runtime version of it might still not be. I’d prefer a single source-of-truth.

What would be the right tool? I think that would be verifications that would happen in flang-tablegen. If it knows the parser grammar/AST hierarchy rules, it could check it for consistency without having influencing the binary executable.
And this is from someone who would prefer to not have too much code in .td files.

1 Like
7

I think that having all these checks in the C++ sources would be fine to begin with. This would allow it to be a lot more flexible until it’s close to having a final form.

8

There seems to be concencus that its OK to remove KIND from template arguments and instead pass it at runtime. I am going to clean up the PR to eventually remove the draft status. Here are some high-level design decisions that I would like to have confirmed so the discussion does not only happen at the review.

  • Integer<> is replaced by IntegerValue which wraps an llvm::APInt.

  • Logical<>, Complex<> is replaced by LogicalValue, ComplexValue which wrap IntegerValue, RealValue. The original Logical<>/Complex<> also just wrappers around Integer<>, Real<>.

  • CharacterValue is a wrapper of a std::variant<std::monostate_t,std::string,std::u16string,std::u32string> since there is no “arbitrary bitwidth” string class. The monostate is needed because the class needs to be default-initializable, but without a kind argument we don’t know yet by which string type it will be represented. It will be known when assigning a value.

  • Real<> and llvm::APFloat have subtle differene in how they implement rounding and exception flags in corner cases, which make them non-interchangable. APFloat is also missing some operations such as sqrt. At this point in time, I would try to avoid adapting llvm::APFloat and instead use the same trick as CharacterValue: A RealValue wraps a std::variant<> of all possible Real<> classes: Real<2>, Real<3>, Real<4>, Real<8>, Real<10>, Real<2>. This requires us to keep the Real<>andInteger<> implementations (Real<>usesInteger<>as storage backing). This also stop us at the moment to rename RealValue to Real, unless we would renameReal<>` to something else before.

  • To avoid that CharacterValue and RealValue need to include the std::variant, std::string, std::u16string, std::u32string, and Real<>, to be included into every header that uses them, I use a pImpl-inspired scheme to abstract over the implementation. In contrast to a pointer of the implementation, it casts itself over an opaque object of the same size. The size is determined automatically at configure-time, and verified at compile-time with a static_assert. This way only one TU needs the heavy lifting of the std::variant implementation. The static_assert is similarly already employed in a related use case in Flang-RT: llvm-project/flang-rt/include/flang-rt/runtime/array-constructor.h at 44cb124f6052b789832a742f39478d88dc94662a · llvm/llvm-project · GitHub

2 Likes
9

I think a massive change like this cannot be one time massive PR. No one will be able to review it properly and it’ll be very difficult to shake out any bugs due to sheer number of changes.

This itself is a pretty fundamental implementation change and should be its own PR that runs through all possible testing (SPEC, apps, Fujitsu, etc.). Current integer implementation is very much tuned to Fortran behaviors.

10

I had AI agent do a deep review of the refactoring PR with concentration on correctness. It found cases where flang currently passes but the refactored code doesn’t. This PR contains these cases, so it should be easier to catch things in the future: [flang] Add kind-preservation regression tests by eugeneepshteyn · Pull Request #208760 · llvm/llvm-project · GitHub

1 Like
11

Refactoring of central classes will always be massive. If we don’t think we are able to review lots code line changes, we will not even be able to do even simple rename.

My goal is to make the changes quite mechanical. That is, in principle, KIND template parameter → kind function argument or kind_ class member (or some other source if it’s know to be the same). Despite my instruction to the AI to focus on correctness, it preferred to look for random sources that are named kind-something and happend to work a lot of times. That’s why I am currently doing a manual overhaul which, as mentioned, should be rather mechanical.

I think the new test cases will be quite useful, thanks for the effort.

I do not share this concern. Both integer implementations (Integer<> and APInt) implement the register semantics of the underlaying hardware. It needs to be “tuned” to accurately represent the instruction set. Neither Fortran nor C/C++ is trying to abstract over one’s complement vs two’s complement, little vs big endiant, etc.
This is a lot easier for integer since hardware nowadays has converged on two’s complement with few operations that are implementation-defined (division-by-zero, shift/rotate exceeding bitwidth, etc) but it is very same problem that LLVM/Clang had to tackle as well. Integer<> and APInt have a very similar interface already. It’s not that we are inventing any new integer operations.

Real<> vs APFloat is another issue because the IEEE standard has room for implementation-defined behaviour in rounding and exception flags. Flang’s Real<> very carefully emulates what Intel and AMD processors do under x86_64, while APFloat diverges here. Other processors, including x86 implementations from other vendors, could have diverged.
This is why I am NOT proposing to replace Real<> for now.