[RFC] Compress Intrinsic Name Table
This RFC proposes changes in the intrinsic emitter and LLVM Core to reduce the size of the intrinsic name table. The scope is reasonably small, but the proposed IntrinsicName class below I think warrants a review before we can implement this (as well as whether this is worth doing in the first place).
Background and Motivation
LLVM’s TableGen intrinsic emitter backend generates a table of intrinsic names that is #included in the Intrinsics.cpp file and is used to get the base name of intrinsics given the Intrinsic::ID and for looking up an intrinsic (i.e., name → Intrinsic::ID mapping). LLVM intrinsic names follow a naming convention:
intrinsic_name ::= "llvm" ['.' target_prefix]? '.' suffix
The intrinsic name table is an array of C strings, sorted by Intrinsic::ID and containing the base name of the intrinsic. The only exception is intrinsic #0, which is an invalid intrinsic, and its name is defined to be "not_intrinsic". (For overloaded intrinsics, base name is the name without the mangling suffix. For non-overloaded intrinsics, their name is same as base name).
This name table currently is ~385 KB of static data. The motivation for this RFC is that the name table contains redundant data in the form of the llvm. prefix for all strings, and .target prefix for all intrinsics for a given target. If we can eliminate these fixed known pieces from the table, the name table can potentially be reduced to 232KB, which is a 40% reduction in the size.
Additionally, when the llvm.target. prefix is stripped, there could be additional opportunities to compress the name table by using either StringToOffetTable or SequenceToOffsetTable classes to emit the string table (which dedup identical string and strings with a common suffix respectively).
Proposal
The proposal essentially is to do the above, where the emitted intrinsic name table will contain just the suffix portion of the name. On the LLVM Core side, this entails changes to functions that consume IntrinscNameTable.
- For
lookupIntrinsicIDandlookupLLVMIntrinsicByName, we already skip over thellvm.targetsuffix, so it should be straightforward to adopt this change in those functions (by first strippingllvm.target.fromName). - The
Intrinsic::getNameandIntrinsic::getBaseNamefunctions return aStringRefthat points to one of the entries in theIntrinsicNameTable, so that would need to be changed. One option is to change these to return astd::string, but that has a runtime overhead of needing to materialize the entire name of the intrinsic every time this function is called. Other option is to defer that materialization till needed by adding a newTwinelike class that represents the intrinsic name using its components (we cannot useTwinehere as explained in the comment inTwine.hsince it holds pointers to temporary stack objects).
class IntrinsicName {
const StringRef TargetPrefix;
const Stringref Suffix; // First '.' stripped out.
// Allow implicit conversion to std::string.
std::string operator() const {
if (TargetPrefix.empty())
return "llvm." + Suffix;
else
return "llvm." + TargetPrefix + "." + Suffix;
}
};
raw_ostream &operator<<(raw_ostream &OS, const IntrinsicName&);
Both getBaseName() and getName() will now return an IntrinsicName as opposed to a StringRef. They will lookup the Suffix by indexing into the IntrinsicNameTable array, and the TargetPrefix with a binary search in the TargetInfos table that is also generated by the intrinsic emitter and which captures, per target, the range of Intrinsic::ID that belong to that target (and has TargetPrefix as one of the fields in the table entry).
That means the cost of getBaseName will increase from O(1) to O(log(T)) where T is the number of targets, which is generally small (currently 20).
The automatic std::string conversion is the deferred materialization that will kick in for code like:
M.getFunction(Intrinsic::getName(Intrinsic::type_test)))
The << operator will help avoid materializing the name for code like:
OS << "intrinsic(@" << Intrinsic::getBaseName(ID) << ')';
This means that the change should mostly be limited to the Intrinsics.cpp and Intrinsics.h files. If need be, additional functions can be added to this class (for ex, equality and other comparison with StringRef).
Open question
Handling of “not_intrinsic”. The name of the invalid intrinsic does not fit in the naming convention assumed. To accommodate that, we can add a bool to IntrinsicName to encode "not_intrinsic" and preserve the current behavior. However, the name "not_intrinsic" does not seem to be used anywhere, so under the new scheme, another option can also be that we can change it to "llvm.not_intrinsic", but that would change the behavior of code like:
auto *F = M.getFunction(Intrinsic::getName(Intrinsic::not_intrinsic)))
errs() << F->isIntrinsic() << '\n';
With the current code, this prints 0, since the name returned does not have a “llvm.” prefix, so it’s not considered an intrinsic. With the proposed change, it will be considered an intrinsic. Note that in both cases F->getIntrinsicID() will still return Intrinsic::not_intrinsic.
Staging
If the proposal is accepted, we can stage the implementation as follows.
- [Prep]: Address the open question by changing current “not_intrinsic” to “llvm.not_intrinsic” and see if it works If not, we need another bool in the
IntrinsicNameto encode"not_intrinsic"string. - Implement this proposal as is.
- Add support for additional coincidental compression using
StringToOffsetTable, so that common suffix is deduped, as well as suffix that’s a suffix of another one is shared (using
StringToOffsetTable). We will experiment with both and decide (use either one of them or none if it does not provide additional benefit). This should not need any changes to LLVM Core.