llvm-tblgen is still too slow in the default debug build configuration

[rnk]

Bugzilla Link	28222
Version	trunk
OS	Windows NT
Depends On	#38383 #43973 #49312
Blocks	#33939
CC	@ahmedbougacha,@llvm-beanz,@topperc,@davidchisnall,@jryans,@kparzysz-quic,@RKSimon,@MatzeB,@cooperp,@sanjoy

Extended Description

I'm filing this bug because I bothered to build LLVM in debug mode on Windows, and it's ridiculously slow. This has been a persistent problem across LLVM's entire history, and many people have attempted to solve it, but it still persists. Currently we have LLVM_OPTIMIZED_TABLEGEN, but this is off by default and doesn't play well with ninja.

I think we need should solve this by building lib/Support in both release and debug configurations when we detect that the user is building in a debug configuration. The release version of support would be linked into llvm-tblgen. We would also optimize the code in lib/TableGen, which changes infrequently and doesn't need to be debugged very often. We would also disable things like debug iterator checks to make these libraries faster.

We'd probably disable this complexity in an "expensive checks" build. We also don't want to do this when the user is already doing a release build, since it increases the total compilation work.

[MatzeB]

Did someone check yet why tablegen is so slow and whether there is room to improve algorithms? If that is possible it would be a simpler solution than making the build system more complex...

[MatzeB]

Case in point: Around 10 minutes with a profilier (and the usual extra 20 minutes to check the changes for correctness), resulting in r273235 which cuts the runtime of the two slowest tblgen invocations in half in my debug build.

(And yes I do debug tblegen from time to time and I had my share of bugs in LLVM_OPTIMIZED_TABLEGEN when it was newly introduced, not sure if it behaves better nowadays).

[ahmedbougacha]

There are probably still low-hanging fruits, but one known problem is that too much (everything but MC/Object?) unnecessarily depends on intrinsics_gen.

Another one that has bothered me for years is that we re-run tablegen on all target .td files for every .inc generated, whereas they all do the same initial parse (I'm pretty sure the RecordKeeper is effectively immutable in all backends).

Some even share the same (expensive) data structure (CodeGenDAGPatterns). That's also mostly const, so we could in theory reuse all of that.

Some of the backends (e.g., Subtarget/RegisterInfo) don't do much more than iterate over some derived definitions, so these are dominated by the parse time. Others have more custom logic (AsmMatcher/DAGISel) but it looks like there's still ~30% (1/3min) spent on parsing.

Even though you'd serialize the tablegens, it could still be a win to run say -gen-subtarget/-gen-register-info or (trickier) -gen-dag-isel/-gen-instr-info back to back in the same process.

I tried just emitting both back to back to the same .inc:

-gen-dag-isel -gen-instr-info:     3m49s (2m04s+1m45s)  ->  2m46s
-gen-subtarget -gen-register-info: 2m31s (1m27s+1m04s)  ->  1m27s

[cooperp]

Definitely worth speeding up tablegen, but we should also fix some of the dependencies.

For example, AttrImpl.inc in clang thinks it depends on these .td files:

../include/llvm/CodeGen/ValueTypes.td
../include/llvm/IR/Attributes.td
../include/llvm/IR/Intrinsics.td
../include/llvm/IR/IntrinsicsAArch64.td
../include/llvm/IR/IntrinsicsAMDGPU.td
../include/llvm/IR/IntrinsicsARM.td
../include/llvm/IR/IntrinsicsBPF.td
../include/llvm/IR/IntrinsicsHexagon.td
../include/llvm/IR/IntrinsicsMips.td
../include/llvm/IR/IntrinsicsNVVM.td
../include/llvm/IR/IntrinsicsPowerPC.td
../include/llvm/IR/IntrinsicsSystemZ.td
../include/llvm/IR/IntrinsicsWebAssembly.td
../include/llvm/IR/IntrinsicsX86.td
../include/llvm/IR/IntrinsicsXCore.td
../include/llvm/Option/OptParser.td
../include/llvm/Target/GenericOpcodes.td
../include/llvm/Target/Target.td
../include/llvm/Target/TargetCallingConv.td
../include/llvm/Target/TargetItinerary.td
../include/llvm/Target/TargetSchedule.td
../include/llvm/Target/TargetSelectionDAG.td
../tools/clang/include/clang/AST/CommentCommands.td
../tools/clang/include/clang/AST/CommentHTMLNamedCharacterReferences.td
../tools/clang/include/clang/AST/CommentHTMLTags.td
../tools/clang/include/clang/Basic/Attr.td

But when you use -d in tablegen (thanks Ahmed for that!) it only actually depends on:

llvm/tools/clang/include/clang/AST/../..//clang/Basic/AttrDocs.td llvm/tools/clang/include/clang/AST/../..//clang/Basic/DeclNodes.td llvm/tools/clang/include/clang/AST/../..//clang/Basic/StmtNodes.td

So we have some CMake hacking to do to get these deps in a much better state.

[llvmbot]

It'd be hard for cmake to give more accurate deps.

Could we implement "smart cache" in tblgen?

[llvm-beanz]

I don't think it would be hard to do more granular dependencies in tablegen generation, which might help the problem. It is sadly a good bit of work detangling some odd code, and it will have Cross-project dependencies because it will impact all tablegen tools.

[llvmbot]

Reid, does it work?

--- a/llvm/cmake/modules/TableGen.cmake
+++ b/llvm/cmake/modules/TableGen.cmake
@@ -131,6 +131,17 @@ macro(add_tablegen target project)
       add_custom_target(${project}-tablegen-host DEPENDS ${${project}_TABLEGEN_EXE})
       set(${project}_TABLEGEN_TARGET ${project}-tablegen-host PARENT_SCOPE)
     endif()
+  elseif(LLVM_OPTIMIZED_TABLEGEN AND CMAKE_CONFIGURATION_TYPES)
+    set(${project}_TABLEGEN_EXE "${CMAKE_BINARY_DIR}/Release/bin/${target}${CMAKE_EXECUTABLE_SUFFIX}")
+    set(${project}_TABLEGEN_EXE ${${project}_TABLEGEN_EXE} PARENT_SCOPE)
+    message("project: ${project}")
+    message("tblgen: ${${project}_TABLEGEN_EXE}")
+    add_custom_command(OUTPUT ${${project}_TABLEGEN_EXE}
+      COMMAND ${CMAKE_COMMAND} --build . --target ${target} --config Release
+      WORKING_DIRECTORY ${CMAKE_BINARY_DIR}
+      COMMENT "Building Release TableGen...")
+    add_custom_target(${project}-tablegen-optimized DEPENDS ${${project}_TABLEGEN_EXE})
+    set(${project}_TABLEGEN_TARGET ${project}-tablegen-optimized PARENT_SCOPE)
   endif()

   if( MINGW )

[rnk]

I tried that patch, but I'm using ninja, not msbuild, so cmake --build NATIVE --config Release doesn't actually work, and I get a debug llvm-tblgen.exe which is still too slow.

The native build also uses the default compiler (MSVC in my case) instead of clang, which my main build is configured to use.

I think in general LLVM_OPTIMIZED_TABLEGEN can't be on by default because it doesn't generate a single ninja build file.

(As of this writing llvm-tblgen still hasn't finished.)

[rnk]

With some effort I managed to use Windows profiling tools to determine that all the tblgen time is spent in MSVC STL debug iterator checks. So, we can fix this problem by switching to LLVM's own ADT or turning off the debug iterators in LLVM. Of course, we might not want to do that if they catch bugs.

[llvm-beanz]

Reid,

While you're right that --config Release doesn't do anything for Ninja, the NATIVE build directory is configured with CMAKE_BUILD_TYPE=Release, so you should still get a release tablegen out of it (CrossCompile.cmake:42).

All the CrossCompile goop needs improvement, and should be mostly rewritten. We should be feeding in CMAKE_*_COMPILER and a handful of other variables too.

I disagree with your statement that we can't use it as the default just because it generates multiple ninja files. Our build is moving in the direction of generating multiple configuration directories and having ninja invoking sub-ninjas is part of that. We have lots of places in the build that do this today (LLVM_BUILD_EXTERNAL_COMPILER_RT, CLANG_ENABLE_BOOTSTRAP, the new runtimes subdirectory).

I expect we'll be getting more of these situations in the future, not less. Someday in the future maybe CMake will provide features to allow us to import sub-ninja projects into the main ninja. That would be awesome, but until then, ninja invoking ninja is our path.

[rnk]

I expect we'll be getting more of these situations in the future, not less.
Someday in the future maybe CMake will provide features to allow us to
import sub-ninja projects into the main ninja. That would be awesome, but
until then, ninja invoking ninja is our path.

I think this erodes the value proposition of ninja as a build system, though. I suspect as you go down this road I won't be the only one who is going to try to maintain a way to configure the build without any cross-compile stuff.

[ahmedbougacha]

With some effort I managed to use Windows profiling tools to determine that
all the tblgen time is spent in MSVC STL debug iterator checks. So, we can
fix this problem by switching to LLVM's own ADT or turning off the debug
iterators in LLVM. Of course, we might not want to do that if they catch
bugs.

I don't think they ever did (grepping the log seems to confirm that), and tblgen is rarely modified. I'd just disable the checks.

[rnk]

I don't think they ever did (grepping the log seems to confirm that), and
tblgen is rarely modified. I'd just disable the checks.

Switching to SmallVector in 'class Record' does 90% of the trick.

The next issue I encountered was this crazy fixpoint iteration in DAGISelMatcherEmitter:

      // We need to encode the child and the offset of the failure code before
      // emitting either of them.  Handle this by buffering the output into a
      // string while we get the size.  Unfortunately, the offset of the
      // children depends on the VBR size of the child, so for large children we
      // have to iterate a bit.
      SmallString<128> TmpBuf;
      unsigned ChildSize = 0;
      unsigned VBRSize = 0;
      do {
        VBRSize = GetVBRSize(ChildSize);

        TmpBuf.clear();
        raw_svector_ostream OS(TmpBuf);
        formatted_raw_ostream FOS(OS);
        ChildSize = EmitMatcherList(SM->getChild(i), Indent+1,
                                    CurrentIdx+VBRSize, FOS);
      } while (GetVBRSize(ChildSize) != VBRSize);

Profiling shows that the mutual recursion between EmitMatcher and EmitMatcherList can get on the stack up to 10 times, and that all the buffered ostream writing is expensive. It seems like we could save some work here if we were clever.

[llvmbot]

I had recently to build on Windows and I was annoyed by the crappy performances, e.g.

fluttershy@Sony-PC MINGW64 /C/Users/fluttershy/work/llvm/build-ninja (master)
$ time /c/Users/fluttershy/work/llvm/build-ninja/bin/llvm-tblgen.exe -gen-dag-isel -I /c/Users/fluttershy/work/llvm/lib/Target/X86 -I /c/Users/fluttershy/work/llvm/lib/Target -I /c/Users/fluttershy/work/llvm/include /c/Users/fluttershy/work/llvm/lib/Target/X86/X86.td -o "/c/Users/fluttershy/work/llvm/build-ninja/lib/Target/X86/X86GenDAGISel.inc.tmp"

real    3m19.233s
user    0m0.015s
sys     0m0.000s

A Vtune profile showed up a lot of time spent into PointerIntPair* code, in particular PointerIntPair<Init *, 1, bool> NameAndPrefix (llvm/TableGen/Record.h).

Reid suggested that we could do a map<Init *, RecordVal *> instead and benchmark again.
Another idea (always by Reid) is to pass a null ostream to recursive calls to avoid all the formatting logic and just calculate the length of the nested entries).

Writing these ideas here so that they don't get lost (and I don't forget :)

[RKSimon]

Definitely worth speeding up tablegen, but we should also fix some of the
dependencies.

Did anything ever happen with splitting up tablegen dependencies?