Changing a header file somewhere and having to spend 10 minutes waiting for a build leads to a lot of wasted developer time.
The real culprit here is tablegen. Can we split support and ADT into two - the parts that tablegen depends on and the parts that it doesn’t?
From what I can gather, Tablegen currently depends on these headers and all of their transitive dependencies.
#include “llvm/Support/Casting.h”
#include “llvm/Support/CommandLine.h”
#include “llvm/Support/Compiler.h”
#include “llvm/Support/DataTypes.h”
#include “llvm/Support/Debug.h”
#include “llvm/Support/Error.h”
#include “llvm/Support/ErrorHandling.h”
#include “llvm/Support/Format.h”
#include “llvm/Support/FormattedStream.h”
#include “llvm/Support/LEB128.h”
#include “llvm/Support/LowLevelTypeImpl.h”
#include “llvm/Support/ManagedStatic.h”
#include “llvm/Support/MathExtras.h”
#include “llvm/Support/MemoryBuffer.h”
#include “llvm/Support/PrettyStackTrace.h”
#include “llvm/Support/Regex.h”
#include “llvm/Support/SMLoc.h”
#include “llvm/Support/ScopedPrinter.h”
#include “llvm/Support/Signals.h”
#include “llvm/Support/SourceMgr.h”
#include “llvm/Support/raw_ostream.h”
#include “llvm/ADT/APInt.h”
#include “llvm/ADT/ArrayRef.h”
#include “llvm/ADT/BitVector.h”
#include “llvm/ADT/CachedHashString.h”
#include “llvm/ADT/DenseSet.h”
#include “llvm/ADT/IndexedMap.h”
#include “llvm/ADT/IntEqClasses.h”
#include “llvm/ADT/MapVector.h”
#include “llvm/ADT/Optional.h”
#include “llvm/ADT/PointerUnion.h”
#include “llvm/ADT/STLExtras.h”
#include “llvm/ADT/SetVector.h”
#include “llvm/ADT/SmallPtrSet.h”
#include “llvm/ADT/SmallSet.h”
#include “llvm/ADT/SmallVector.h”
#include “llvm/ADT/SparseBitVector.h”
#include “llvm/ADT/Statistic.h”
#include “llvm/ADT/StringExtras.h”
#include “llvm/ADT/StringMap.h”
#include “llvm/ADT/StringRef.h”
#include “llvm/ADT/StringSet.h”
#include “llvm/ADT/StringSwitch.h”
#include “llvm/ADT/TinyPtrVector.h”
#include “llvm/ADT/Twine.h”
Is this something worth putting effort into? If so, I volunteer.
What’s the actual problem here? Is it that TableGen regenerates different files and so we then need to rebuild all dependencies of those files? Maybe we should use a diff-and-update approach (I thought, however, that we already did that). -Hal
It’s that TableGen depends on Support, so if you change one file in support, support gets recompiled into a new static archive, which triggers a rerun of tablegen on all the tablegen inputs, which is extremely slow.
I thought that we had a “build an optimized tablegen even in debug mode” setting to work around this problem. Would that avoid this problem? -Hal
It would be better, because a debug tablegen is slower than an optimized tablegen, but it’s still slow and it doesn’t address the problem that tablegen runs at all when it doesn’t really need to. I think if tablegen wasn’t running all the time we could incremental builds down from 15 minutes (and that’s on my really powerful machine) to under 5, which seemed like a big productivity boost averaged out over all users x time
We’ve got a lot of random stuff in Support, not all really related and not all relevant to every project. It seems like we should be able to do better.
That certainly makes sense. I wonder, however, if we could have a more principled decomposition (instead of just “What’s used by TableGen” vs. “What’s not used by TableGen”). -Hal
In FreeBSD we use a 'minimal' llvm library for this purpose:
https://github.com/freebsd/freebsd/blob/master/lib/clang/libllvmminimal/Makefile
This contains just the .c and .cpp files which are dependencies of llvm-tbglen and clang-tblgen. The header dependencies aren't in there, those are generated using -MD.
-Dimitry
It would be better, because a debug tablegen is slower than an optimized tablegen, but it’s still slow and it doesn’t address the problem that tablegen runs at all when it doesn’t really need to. I think if tablegen wasn’t running all the time we could incremental builds down from 15 minutes (and that’s on my really powerful machine) to under 5, which seemed like a big productivity boost averaged out over all users x time
Is that 10 minutes of running tablegen, though? I think this touches on Hal’s comment:
“Maybe we should use a diff-and-update approach (I thought, however, that we already did that).”
In that the 10 minutes is presumably from timestamp-based invalidation chaining down from running tablegen, to then rebuilding everything that depends on tablegen’s output.
That could be addressed by either the build system or tablegen writing output to a temporary file, comparing the temp to the current file, and not modifying the current file if they’re the same - thus not invalidating everything down the chain that depends on the tablegen output (not sure if that’s actually enough to convince a build system not to rebuild other things - but worth a shot). This is a bit of a hackaround what the build system itself could/should be doing, but in the absence of a content based invalidation scheme - addressing this one particularly critical point in LLVM’s build seems like it could be worth such a workaround. (this would speed up the build for even the times when tablegen’s real dependencies change - add a new function to ArrayRef, or STLExtras, etc… and tablegen runs, but it doesn’t cascade to everything else).
(plus, opt build of tablegen, so that conclusion can be reached more quickly)
As Hal also mentioned, I’d be OK with this if there’s a good logical division that can be taken more than “whatever is/isn’t used in tablegen”.
I thought we already did write tablegen output to temporary files like X86GenAsmWriter1.inc.tmp first and then diffed them with the real .inc file and conditionally copied.
Maybe we do and build systems aren’t respecting/noticing this? I’m not sure.
I think there are logical ways of splitting, but taken individually they would be rather small. For example, threading support, i/o related support, file system support.
At the same time, when you look at support there’s kind of some glaringly obvious differences in how “low level” the various things are. Compiler.h is pretty low level. Dwarf.h, not so much. It’s hard to really quantify this, but I could certainly imagine introducing something even more low level than Support, perhaps with a name like Base
What exactly is extremely slow? In my experience TableGen itself takes a negligible amount of time compared to the rest of the build. This is particularly true in cases when something in Support or ADT is modified, as this usually triggers recompilation of large parts of LLVM.
-Krzysztof
2017-05-26 17:47 GMT-07:00 Zachary Turner via llvm-dev <llvm-dev@lists.llvm.org>:
Changing a header file somewhere and having to spend 10 minutes waiting for a build leads to a lot of wasted developer time.
The real culprit here is tablegen. Can we split support and ADT into two - the parts that tablegen depends on and the parts that it doesn’t?
Splitting ADT just based on tablegen usage seems dubious to me. If we need to go this route, I’d replace as many uses of ADT data structure with STL ones to begin with to reduce the surface.
2017-05-26 17:47 GMT-07:00 Zachary Turner via llvm-dev <llvm-dev@lists.llvm.org>:
Changing a header file somewhere and having to spend 10 minutes waiting for a build leads to a lot of wasted developer time.
The real culprit here is tablegen. Can we split support and ADT into two - the parts that tablegen depends on and the parts that it doesn’t?
Splitting ADT just based on tablegen usage seems dubious to me. If we need to go this route, I’d replace as many uses of ADT data structure with STL ones to begin with to reduce the surface.
Tablegen would not need to determine WHERE to split, it would just motivate the why. It’s obvious just from looking at Support’s include directory though that a lot of stuff in there doesn’t belong together. A quick look over the include directory already suggests a split into “broadly useful stuff” and “narrowly useful stuff”
Broadly useful stuff:
AlignOf
Allocator
ArrayRecycler
Atomic
AtomicOrdering
Capacity
Casting
Chrono
circular_raw_ostream
COM.h
CommandLine.h
Compiler.h
ConvertUTF.h
CrashRecoveryContext.h
DataExtractor.h
Debug.h
Endian.h
EndianStream.h
Errc.h
Errno.h
Error.h
ErrorHandling.h
ErrorOr.h
FileOutputBuffer.h
FileSystem.h
FileUtilities.h
Format*.h
GlobPattern.h
Host.h
JamCRC.h
KnownBits.h
LineIterator.h
Locale.h
ManagedStatic.h
MathExtras.h
MD5.h
Memory.h
MemoryBuffer.h
Mutex.h
MutexGuard.h
NativeFormatting.h
Options.h
Parallel.h
Path.h
PointerLikeTypeTraits.h
PrettyStackTrace.h
Printable.h
Process.h
Program.h
RandomNumberGenerator.h
raw_os_ostream.h
raw_ostream.h
raw_sha1_ostream.h
Recycler.h
RecyclingAllocator.h
Regex.h
RWMutex.h
SaveAndRestore.h
ScaledNumber.h
SHA1.h
Signals.h
StringPool.h
StringSaver.h
SwapByteOrder.h
SystemUtils.h
thread.h
Threading.h
ThreadLocal.h
ThreadPool.h
Timer.h
TrailingObjects.h
Unicode.h
UnicodeCharRanges.h
UniqueLock.h
Watchdog.h
Win64EH.h
WindowsError.h
xxhash.h
Narrowly useful stuff:
AArch64TargetParser.def
ARMAttributeParser.h
ARMBuildAttriubtes.h
ARMEHABI.h
ARMTargetParser.def
ARMWinEH.h
BinaryStream.h
BlockFrequency.h
BranchProbability.h
CachePruning.h
CBindingWrapping.h
CodeGen.h
CodeGenCWrappers.h
COFF.h
Compression.h
DebugCounter.h
DotGraphTraits.h
Dwarf.def
Dwarf.h
DynamicLibrary.h
ELF.h
GCOV.h
GenericDomTree.h
GenericDomTreeConstruction.h
GraphWriter.h
LEB128.h
LockFileManager.h
LowLevelTypeImpl.h
MachO.def
MachO.h
MipsABIFlags.h
OnDiskHashTable.h
PluginLoader.h
Registry.h
ScopedPrinter.h
SMLoc.h
Solaris.h
SourceMgr.h
SpecialCaseList.h
TargetParser.h
TargetRegistry.h
TargetSelect.h
TarWriter.h
ToolOutputFile.h
TrigramIndex.h
TypeName.h
Valgrind.h
Wasm.h
YAMLParser.h
YAMLTraits.h
So, as a very crude first attempt, you call the first group of stuff “Base”, the second group “Support”, and add a dependency from Support to Base. This has nothing to do with tablegen, btw, and tablegen would still probably depend on Support even after this separation, but it makes sense even from a high level layering perspective (IMO)
2017-05-26 17:47 GMT-07:00 Zachary Turner via llvm-dev <
llvm-dev@lists.llvm.org>:
Changing a header file somewhere and having to spend 10 minutes waiting
for a build leads to a lot of wasted developer time.
The real culprit here is tablegen. Can we split support and ADT into
two - the parts that tablegen depends on and the parts that it doesn't?
Splitting ADT just based on tablegen usage seems dubious to me. If we
need to go this route, I'd replace as many uses of ADT data structure with
STL ones to begin with to reduce the surface.
Tablegen would not need to determine WHERE to split, it would just
motivate the why.
Well even the why 
(note I was mentioning ADT and not Support above).
It's obvious just from looking at Support's include directory though
that a lot of stuff in there doesn't belong together. A quick look over
the include directory already suggests a split into "broadly useful stuff"
and "narrowly useful stuff"
I agree, Support is a mess IMO (we have target specific stuff here just for
the sake of sharing code with clang AFAIK) and I'm not sure anyone would
oppose to split it. Ideally the way I would split it would be such that it
could (at some point) be useful outside of LLVM (just like ADT), so one
main criteria could be "could this component of Support be useful outside
of LLVM (and its subprojects)".
Broadly useful stuff:
AlignOf
Allocator
ArrayRecycler
Atomic
AtomicOrdering
Capacity
Casting
Chrono
circular_raw_ostream
COM.h
CommandLine.h
Compiler.h
ConvertUTF.h
CrashRecoveryContext.h
DataExtractor.h
Debug.h
Endian.h
EndianStream.h
Errc.h
Errno.h
Error.h
ErrorHandling.h
ErrorOr.h
FileOutputBuffer.h
FileSystem.h
FileUtilities.h
Format*.h
GlobPattern.h
Host.h
JamCRC.h
KnownBits.h
LineIterator.h
Locale.h
ManagedStatic.h
MathExtras.h
MD5.h
Memory.h
MemoryBuffer.h
Mutex.h
MutexGuard.h
NativeFormatting.h
Options.h
Parallel.h
Path.h
PointerLikeTypeTraits.h
PrettyStackTrace.h
Printable.h
Process.h
Program.h
RandomNumberGenerator.h
raw_os_ostream.h
raw_ostream.h
raw_sha1_ostream.h
Recycler.h
RecyclingAllocator.h
Regex.h
RWMutex.h
SaveAndRestore.h
ScaledNumber.h
SHA1.h
Signals.h
StringPool.h
StringSaver.h
SwapByteOrder.h
SystemUtils.h
thread.h
Threading.h
ThreadLocal.h
ThreadPool.h
Timer.h
TrailingObjects.h
Unicode.h
UnicodeCharRanges.h
UniqueLock.h
Watchdog.h
Win64EH.h
WindowsError.h
xxhash.h
Narrowly useful stuff:
AArch64TargetParser.def
ARMAttributeParser.h
ARMBuildAttriubtes.h
ARMEHABI.h
ARMTargetParser.def
ARMWinEH.h
Binary*Stream*.h
BlockFrequency.h
BranchProbability.h
CachePruning.h
CBindingWrapping.h
CodeGen.h
CodeGenCWrappers.h
COFF.h
Compression.h
DebugCounter.h
DotGraphTraits.h
Dwarf.def
Dwarf.h
DynamicLibrary.h
ELF.h
GCOV.h
GenericDomTree.h
GenericDomTreeConstruction.h
GraphWriter.h
LEB128.h
LEB128.h seems quite generic.
LockFileManager.h
LowLevelTypeImpl.h
MachO.def
MachO.h
MipsABIFlags.h
OnDiskHashTable.h
PluginLoader.h
Registry.h
ScopedPrinter.h
SMLoc.h
Solaris.h
SourceMgr.h
SpecialCaseList.h
TargetParser.h
TargetRegistry.h
TargetSelect.h
TarWriter.h
ToolOutputFile.h
TrigramIndex.h
TypeName.h
Valgrind.h
Wasm.h
YAMLParser.h
YAMLTraits.h
YAML Parser as well.
YAML Parser is only used by things that need to parse YAML, which while in principle might seem generic, is actually only used by a small number of tools. Besides, if you’re bringing in YAML to parse something, then you’re probably linking against some library like libObject, which will in turn link against Support (as I’m referring to it in this thread, not as it exists today).
It might turn out though that in practice it would be hard to keep it out of Base, because for example even Statistic uses it for dumping. I did a quick search and sadly it seems like a lot of libraries include YAML support directly in the library rather than in the tool that dumps the library.
That said, it would be nice if at all possible the barrier to entry for getting something into Base were higher and stricter than the barrier to entry for getting something into Support. So whenever possible we should err on the side of keeping stuff out of base.
2017-05-26 17:47 GMT-07:00 Zachary Turner via llvm-dev <llvm-dev@lists.llvm.org>:
Changing a header file somewhere and having to spend 10 minutes waiting for a build leads to a lot of wasted developer time.
The real culprit here is tablegen. Can we split support and ADT into two - the parts that tablegen depends on and the parts that it doesn’t?
Splitting ADT just based on tablegen usage seems dubious to me. If we need to go this route, I’d replace as many uses of ADT data structure with STL ones to begin with to reduce the surface.
Tablegen would not need to determine WHERE to split, it would just motivate the why. It’s obvious just from looking at Support’s include directory though that a lot of stuff in there doesn’t belong together. A quick look over the include directory already suggests a split into “broadly useful stuff” and “narrowly useful stuff”
Broadly useful stuff:
AlignOf
Allocator
ArrayRecycler
Atomic
AtomicOrdering
Capacity
Casting
Chrono
circular_raw_ostream
COM.h
CommandLine.h
Compiler.h
ConvertUTF.h
CrashRecoveryContext.h
DataExtractor.h
Debug.h
Endian.h
EndianStream.h
Errc.h
Errno.h
Error.h
ErrorHandling.h
ErrorOr.h
FileOutputBuffer.h
FileSystem.h
FileUtilities.h
Format*.h
GlobPattern.h
Host.h
JamCRC.h
KnownBits.h
LineIterator.h
Locale.h
ManagedStatic.h
MathExtras.h
MD5.h
Memory.h
MemoryBuffer.h
Mutex.h
MutexGuard.h
NativeFormatting.h
Options.h
Parallel.h
Path.h
PointerLikeTypeTraits.h
PrettyStackTrace.h
Printable.h
Process.h
Program.h
RandomNumberGenerator.h
raw_os_ostream.h
raw_ostream.h
raw_sha1_ostream.h
Recycler.h
RecyclingAllocator.h
Regex.h
RWMutex.h
SaveAndRestore.h
ScaledNumber.h
SHA1.h
Signals.h
StringPool.h
StringSaver.h
SwapByteOrder.h
SystemUtils.h
thread.h
Threading.h
ThreadLocal.h
ThreadPool.h
Timer.h
TrailingObjects.h
Unicode.h
UnicodeCharRanges.h
UniqueLock.h
Watchdog.h
Win64EH.h
WindowsError.h
xxhash.h
Narrowly useful stuff:
AArch64TargetParser.def
ARMAttributeParser.h
ARMBuildAttriubtes.h
ARMEHABI.h
ARMTargetParser.def
ARMWinEH.h
BinaryStream.h
BlockFrequency.h
BranchProbability.h
CachePruning.h
CBindingWrapping.h
CodeGen.h
CodeGenCWrappers.h
COFF.h
Compression.h
DebugCounter.h
DotGraphTraits.h
Dwarf.def
Dwarf.h
DynamicLibrary.h
ELF.h
GCOV.h
GenericDomTree.h
GenericDomTreeConstruction.h
GraphWriter.h
LEB128.h
LockFileManager.h
LowLevelTypeImpl.h
MachO.def
MachO.h
MipsABIFlags.h
OnDiskHashTable.h
PluginLoader.h
Registry.h
ScopedPrinter.h
SMLoc.h
Solaris.h
SourceMgr.h
SpecialCaseList.h
TargetParser.h
TargetRegistry.h
TargetSelect.h
TarWriter.h
ToolOutputFile.h
TrigramIndex.h
TypeName.h
Valgrind.h
Wasm.h
YAMLParser.h
YAMLTraits.h
So, as a very crude first attempt, you call the first group of stuff “Base”, the second group “Support”, and add a dependency from Support to Base. This has nothing to do with tablegen, btw, and tablegen would still probably depend on Support even after this separation, but it makes sense even from a high level layering perspective (IMO)
To what end, though? If most things will depend on both anyway - it doesn’t sound like the split would help/improve the situation re: changes to base or support leading to full rebuilds of LLVM… no?
Well you have to start somewhere right? Even if it doesn’t completely solve the issue with TableGen, it is a step towards that, and it does help the issue of Support being a mess with everything under the kitchen sink. After doing that split, I’m going to wager that everything in ADT would depend only on Base (or be very close to depending only on Base), at which point LLVMBase.a can be ac ombination of ADT and Base instead of a combination of ADT and Support, and then you only have to look at the remaining headers in Support to see what tablegen depends on. The original list I posted that tablegen depended on from Support was
#include “llvm/Support/Casting.h”
#include “llvm/Support/CommandLine.h”
#include “llvm/Support/Compiler.h”
#include “llvm/Support/DataTypes.h”
#include “llvm/Support/Debug.h”
#include “llvm/Support/Error.h”
#include “llvm/Support/ErrorHandling.h”
#include “llvm/Support/Format.h”
#include “llvm/Support/FormattedStream.h”
#include “llvm/Support/LEB128.h”
#include “llvm/Support/LowLevelTypeImpl.h”
#include “llvm/Support/ManagedStatic.h”
#include “llvm/Support/MathExtras.h”
#include “llvm/Support/MemoryBuffer.h”
#include “llvm/Support/PrettyStackTrace.h”
#include “llvm/Support/Regex.h”
#include “llvm/Support/SMLoc.h”
#include “llvm/Support/ScopedPrinter.h”
#include “llvm/Support/Signals.h”
#include “llvm/Support/SourceMgr.h”
#include “llvm/Support/raw_ostream.h”
And there’s only 2 or 3 of these that I put on the “narrowly useful” list, so it doesn’t seem that difficult to address from here. (And I came up with that separation without even looking at TableGen’s dependencies, so it seems TableGen already only depends on most of the actually broadly useful stuff).
Of course, TableGen is only part of the build process (albeit the slowest part), I would be rather surprised if a split such as the one proposed (with some inevitable alternations based on user feedback) did not allow various other projects to also remove a dependency on Support in favor of one on Base, which could have a positive trickle down effect on build times for other projects not related to tablegen.
Also, like Mehdi said, it would be nice if there were a way for non LLVM projects to use Support. I one tried to make a program unrelated to LLVM or compilers just for a hobbyist project, and I wanted to link against Support to use things like StringRef, DenseMap, etc, but because of all the added cruft in support, I could never get it even building. The less stuff there is the easier it would be for external projects to benefit from some of LLVM’s common libraries. Obviously this is not an explicitly stated goal of the project, but if it can fall out naturally from otherwise good design principles, why not?
In my experience the buildsystem works fine in combination with tablegen (at least this aspect of it). The real problem here is that tablegen is just slow. Some of the X86 tables take indeed
Last time I looked at it tablegen had still room to optimize the way it resolves class hierarchies and the variables within which it did basically one at a time, so it needed to traverse the hierarchies again for each variables.