Fix non-global-value-max-name-size not considered by LLParser

[hasyimibhar]

Summary

non-global-value-max-name-size is used by Value to cap the length of local value name. However, this flag is not considered by LLParser, which leads to unexpected use of undefined value error. The fix is to move the responsibility of capping the length to ValueSymbolTable.

The test is the one provided by Mikael in the bug report.

[hasyimibhar]

Remove whitespace

[hasyimibhar]

Add description to test

[hasyimibhar]

This is pretty much my first patch for LLVM, so let me know if I'm doing something wrong. The function capLocalValueName is added because I'm not sure how NonGlobalValueMaxNameSize can be exposed outside of Value.cpp.

[uabelho]

Adding the reviewers of
https://reviews.llvm.org/D41296
which introduced the name capping here too.

[mehdi_amini]

llvm/include/llvm/IR/Value.h

859 ↗

(On Diff #346232)

Nit: seems like you can take a StringRef and return a StringRef here. This'll avoid any copy.

llvm/test/Assembler/non-global-value-max-name-size.ll

11

Can you shorten the name and make the test work with something smaller?
I assume this is possible by using -non-global-value-max-name-size=4 or something small like that?

[hasyimibhar]

Use StringRef and simplify test. I also removed inline in the function definition because it's actually causing a linker error (my C++ is a bit rusty).

[hasyimibhar]

Remove duplicate code

[serge-sans-paille]

llvm/lib/AsmParser/LLParser.cpp

3122 ↗

(On Diff #346353)

This is starting to looks like an invariant that should be maintained (or at least checked) by the value symbol table itself, instead of being enforced at callsite.

[hasyimibhar]

llvm/lib/AsmParser/LLParser.cpp

3122 ↗

(On Diff #346353)

I'm not that familiar with the value symbol table. Does it only contain local value names? If yes, then we can just move the check into the lookup function. If it can also contain global value names, then I'm not sure how it can determine whether or not to cap it just from the provided StringRef.

[hasyimibhar]

Fix clang-tidy error

[serge-sans-paille]

llvm/lib/AsmParser/LLParser.cpp

3122 ↗

(On Diff #346353)

It only holds local and args value, so it's fine to apply the check / change in the class itself. But it probably means we need to write a type adapter as the base class is more generic than what we want to implement here. @mehdi_amini does that looks like the right approach to you?

[hasyimibhar]

Move call of capLocalValueName into ValueSymbolTable

[hasyimibhar]

llvm/lib/AsmParser/LLParser.cpp

3122 ↗

(On Diff #346353)

It only holds local and args value, so it's fine to apply the check / change in the class itself.

I moved it into ValueSymbolTable::lookup.

But it probably means we need to write a type adapter as the base class is more generic than what we want to implement here.

I'm not sure what you mean by this. Are you referring to ValueSymbolTable or LLParser?

[mehdi_amini]

llvm/include/llvm/IR/ValueSymbolTable.h

79

The fact that the table lookups would automatically use this but not the insertions looks like a red flag to me. If this is an invariant of the table then it should be private the table and reflected by the API consistently.

[hasyimibhar]

Move capping to ValueSymbolTable

[hasyimibhar]

llvm/include/llvm/IR/ValueSymbolTable.h

79

I moved NonGlobalValueMaxNameSize into ValueSymbolTable, and made it responsible for doing the capping. It looks like the updated name will be propagated back to the Value class (since createValueName is called by Value::setName), so it should be fine to move it.

I also added isLocal argument to ValueSymbolTable::lookup, because it seems that it's also used to look up global value in LLParser, so there must be a way to differentiate between global and local value name lookup.

[hasyimibhar]

Fix clang-tidy error

[serge-sans-paille]

llvm/include/llvm/IR/ValueSymbolTable.h

79

I also added isLocal argument to ValueSymbolTable::lookup, because it seems that it's also used to look up global value in LLParser, so there must be a way to differentiate between global and local value name lookup.

That's why I suggested to create a type adaptor: a type, that derives from ValueSymbolTable

[hasyimibhar]

llvm/include/llvm/IR/ValueSymbolTable.h

79

Ok let me try to do that. Looking at the code, I'm assuming only the Module will use symbol table for looking up global names.

[hasyimibhar]

Add LocalValueSymbolTable

[hasyimibhar]

Run clang-format

[hasyimibhar]

Does anyone know why the test omp_init_lock.c is failing? I have no idea how it's related to the change.

[serge-sans-paille]

llvm/include/llvm/IR/ValueSymbolTable.h

75–80

@mehdi_amini are we fine with making a few methods here virtual? The approach proposed by @hasyimibhar is elegant, but I'm worried about the performance impact.

An alternative would be to have something like (pseudo code)

class LocalValueSymbolTable {
    ValueSymbolTable table;
    public:
      using ValueSymbolTable::size;  // nothing to change for that one
      Value *lookup(StringRef Name) const { // cap then forward to table }
    private:
      ValueName *createValueName(StringRef Name, Value *V); { // cap then forward to table }

[mehdi_amini]

llvm/include/llvm/IR/ValueSymbolTable.h

75–80

+1: let's not make virtual if we can have an adapter class.

Another way to do it is by refactoring the base class for the common methods, and two derived class that implement the specific methods for each case. You only need virtual for the derived method if you actually need to use this class polymorphically (do you?).

[hasyimibhar]

Add isLocal to ValueSymbolTable to differentiate usage

[hasyimibhar]

llvm/include/llvm/IR/ValueSymbolTable.h

75–80

So I tried to do it with adapter class, but it gets messy because the class is used polymorphically in Value.cpp by getSymTab function. With adapter class, Function::getValueSymbolTable will return the adapter class, while Module::getValueSymbolTable will return the base class. So what ends up happening is inside getSymTab, I had to unwrap the adapter class back to the base class, and then in Value::setNameImpl, I had to check if this is a local value, and if so, wrap the symbol table back with the adapter class.

My suggestion to avoid all this mess while still maintaining performance is to just add isLocal private variable to differentiate between local and global value symbol table. This avoids cost of virtual and doesn't require changing the API of lookup.

Also, maybe it's better to just make it explicit and have the constructor accept a maxNameSize argument? For global, we can set this to -1 to indicate no limit.

[hasyimibhar]

Use maxNameSize argument in constructor

[mehdi_amini]

llvm/include/llvm/IR/ValueSymbolTable.h

75–80

OK, but right now this new member is only used for lookups and not insertions, which makes the invariant non-local the class I believe. Can you make sure makeUniqueName has the matching logic so that this is all self contained in the ValueSymbolTable?

[hasyimibhar]

llvm/include/llvm/IR/ValueSymbolTable.h

75–80

The name is already capped in createValueName (in ValueSymbolTable.cpp), which I believe is the insertion part. makeUniqueName happens after the cap, so you can still have name longer than the limit if there's duplicate, but I think that's the correct behavior.

[hasyimibhar]

Use int for maxNameSize

[hasyimibhar]

llvm/include/llvm/IR/ValueSymbolTable.h

137

maxNameSize is an int instead of unsigned because there is a test (llvm/test/Bitcode/value-with-long-name.ll) which checks for the case where -non-global-value-max-name-size=0.

[hasyimibhar]

Fix clang-tidy error

[mehdi_amini]

llvm/include/llvm/IR/ValueSymbolTable.h

75–80

Ah my bad, I missed this somehow!

[hasyimibhar]

Thanks! This is basically my first patch. Now do I just wait for someone to commit on my behalf? Or does it still need more acceptance?

[dim]

For some reason, this commit causes a huge memory usage, and extreme slowdown, when compiling the FreeBSD port math/openturns (https://github.com/openturns/openturns) port; see https://bugs.freebsd.org/261341.

With llvmorg-13-init-11364-g0ce58c52d50 (i.e. just before this commit):

+ /usr/bin/time -l /home/dim/ins/llvmorg-13-init-11364-g0ce58c52d50/bin/clang -O2 -fstack-protector-strong -fno-strict-aliasing -fPIC '-ftemplate-depth=500' -pthread '-fopenmp=libomp' '-std=gnu++14' -c Dlib.ii
       14.16 real        13.96 user         0.19 sys
    363180  maximum resident set size
     61301  average shared memory size
       479  average unshared data size
       617  average unshared stack size
     73221  page reclaims
         1  page faults
         0  swaps
         0  block input operations
         8  block output operations
         0  messages sent
         0  messages received
         0  signals received
         3  voluntary context switches
       156  involuntary context switches

With llvmorg-13-init-11365-g8d257627206:

+ /usr/bin/time -l /home/dim/ins/llvmorg-13-init-11365-g8d257627206/bin/clang -O2 -fstack-protector-strong -fno-strict-aliasing -fPIC '-ftemplate-depth=500' -pthread '-fopenmp=libomp' '-std=gnu++14' -c Dlib.ii
time: command terminated abnormally
      574.34 real       357.02 user       195.51 sys
  50016576  maximum resident set size
     60984  average shared memory size
       477  average unshared data size
       759  average unshared stack size
  31546767  page reclaims
    132341  page faults
         0  swaps
         4  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         1  signals received
    132360  voluntary context switches
      6162  involuntary context switches

I had to terminate the clang process after ~9 minutes, as it was using >115GiB virtual memory, and this was a bit of a risk to crash the (shared) machine I was working on.

Any ideas, before I attempt reducing the ~196,000 line test case? :)

[mehdi_amini]

In D102707#3267278, @dim wrote:

For some reason, this commit causes a huge memory usage, and extreme slowdown, when compiling the FreeBSD port math/openturns (https://github.com/openturns/openturns) port; see https://bugs.freebsd.org/261341.

With llvmorg-13-init-11364-g0ce58c52d50 (i.e. just before this commit):?
...
I had to terminate the clang process after ~9 minutes, as it was using >115GiB virtual memory, and this was a bit of a risk to crash the (shared) machine I was working on.

Any ideas, before I attempt reducing the ~196,000 line test case? :)

This is pretty bad... Can you clarify if your clang is built with assertions or in release mode? By default clang in release mode does not enable value names so this patch should be a no-op.

In non-release mode (or when value names are explicitly enabled), I could see some code path changing in Value::setNameImpl possibly.
Could you take a profile of your clang? Even if your interrupt after 30s the samples should already point to some interesting places...

[dim]

In D102707#3267708, @mehdi_amini wrote:

In D102707#3267278, @dim wrote:

For some reason, this commit causes a huge memory usage, and extreme slowdown, when compiling the FreeBSD port math/openturns (https://github.com/openturns/openturns) port; see https://bugs.freebsd.org/261341.

With llvmorg-13-init-11364-g0ce58c52d50 (i.e. just before this commit):?
...
I had to terminate the clang process after ~9 minutes, as it was using >115GiB virtual memory, and this was a bit of a risk to crash the (shared) machine I was working on.

Any ideas, before I attempt reducing the ~196,000 line test case? :)

This is pretty bad... Can you clarify if your clang is built with assertions or in release mode?

Ah sorry, forgot to mention that, all clang builds I do for bisecting are with assertions enabled (LLVM_ENABLE_ASSERTIONS=ON and CMAKE_BUILD_TYPE=Release). This is also the case for clang in FreeBSD 14-CURRENT (aka our main branch).

By default clang in release mode does not enable value names so this patch should be a no-op.

In non-release mode (or when value names are explicitly enabled), I could see some code path changing in Value::setNameImpl possibly.
Could you take a profile of your clang? Even if your interrupt after 30s the samples should already point to some interesting places...

I'm currently reducing the test case, which seems to go fairly well, I'll post this in a proper github ticket tomorrow, and I'll attempt to get some profiling done.

[dim]

The top 10 list from perf report output shows that it's doing quite a lot of StringMapImpl work:

Samples: 154K of event 'cycles', Event count (approx.): 175175930341
Overhead  Command  Shared Object        Symbol
    22.50%  clang++  clang-14             [.] llvm::StringMapImpl::LookupBucketFor
    17.64%  clang++  libc-2.31.so         [.] __memmove_avx_unaligned_erms
    15.72%  clang++  clang-14             [.] llvm::StringMapImpl::RemoveKey
     3.94%  clang++  [kernel.kallsyms]    [k] prepare_exit_to_usermode
     3.29%  clang++  [kernel.kallsyms]    [k] clear_page_erms
     2.63%  clang++  libc-2.31.so         [.] __memchr_avx2
     2.07%  clang++  [kernel.kallsyms]    [k] native_irq_return_iret
     1.69%  clang++  [kernel.kallsyms]    [k] rmqueue
     1.64%  clang++  [kernel.kallsyms]    [k] sync_regs
     1.56%  clang++  [kernel.kallsyms]    [k] error_entry
     1.55%  clang++  [kernel.kallsyms]    [k] swapgs_restore_regs_and_return_to_usermode
     1.20%  clang++  libc-2.31.so         [.] __memcmp_avx2_movbe
     0.76%  clang++  [kernel.kallsyms]    [k] zap_pte_range.isra.0
     0.74%  clang++  [kernel.kallsyms]    [k] free_pcppages_bulk

My guess is that due to the Name = Name.substr(0, std::max(1u, (unsigned)MaxNameSize)); in createValueName, a great many temporary StringRefs are created and destroyed?

The creduce run is almost finished, I'll go create a ticket now.

[dim]

The creduce run is almost finished, I'll go create a ticket now.

https://github.com/llvm/llvm-project/issues/53406

[mehdi_amini]

My guess is that due to the Name = Name.substr(0, std::max(1u, (unsigned)MaxNameSize)); in createValueName, a great many temporary StringRefs are created and destroyed?

Creating a StringRef is "free".

Your profile shows a great amount of maps lookup though. It can be that the map size exploded for some reason or that we query it much more?

[dim]

In D102707#3269962, @mehdi_amini wrote:

Your profile shows a great amount of maps lookup though. It can be that the map size exploded for some reason or that we query it much more?

Yes, it appears that removing the capping in Value::setNameImpl() is the culprit. Adding debug output shows that this function regularly gets names hundreds of megabytes long! Maybe that is an issue in itself, but it wasn't a problem in the past, because the names were usually capped at 1024 bytes. Later, such similar-looking strings would get a name conflict, but then another unique name would be generated.

llvm/lib/IR/Value.cpp

326

If I put back *this* particular part, the huge memory usage goes away!

It looks like setNameImpl() is called for each and every loop rotation iteration, leading to identifiers like (here they're cutoff at 1024 chars):

for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i_crit_edge.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i_crit_edge.i_crit_edge.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i_crit_edge.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_edge.i_crit_edge.i_crit_edge.i_crit_edge.i_crit_edge.i.for.body.i.i.i.i.i.for.body.i.i.i.i.i_crit_e

However if the capping is not done at this point, the full identifier is sent through the rest of the function!

When I print NameRef().size() to dbgs()) I get sizes of 1 through 260,046,833 (!), so these strings become a huge memory hog. They might get capped later on, but for some reason they still get inserted into ValueMaps, it seems.

llvm/include/llvm/IR/ValueSymbolTable.h

public:
 
   /// A const_iterator over a ValueMap.
   using const_iterator = ValueMap::const_iterator;
 
 /// @}
 /// @name Constructors
 /// @{
 
-  ValueSymbolTable() : vmap(0) {}
+  ValueSymbolTable(unsigned MaxNameSize = 0)
+      : vmap(0), maxNameSize(MaxNameSize) {}
   ~ValueSymbolTable();
 
   /// @}
   /// @name Accessors
   /// @{
 
   /// This method finds the value with the given \p Name in the
   /// the symbol table.
   /// @returns the value associated with the \p Name
   /// Lookup a named Value.
-  Value *lookup(StringRef Name) const { return vmap.lookup(Name); }
+  Value *lookup(StringRef Name) const {
+    if (maxNameSize > 0 && Name.size() > maxNameSize)
+      Name = Name.substr(0, std::max(1u, maxNameSize));
+
+    return vmap.lookup(Name);
+  }
 
   /// @returns true iff the symbol table is empty
   /// Determine if the symbol table is empty
   inline bool empty() const { return vmap.empty(); }
 
   /// The number of name/type pairs is returned.
   inline unsigned size() const { return unsigned(vmap.size()); }
 
private:
   /// symtab.
   void removeValueName(ValueName *V);
 
   /// @}
   /// @name Internal Data
   /// @{
 
   ValueMap vmap;                    ///< The map that holds the symbol table.
+  unsigned maxNameSize; ///< The maximum size for each name. If the limit is
+                        ///< exceeded, the name is capped.
   mutable uint32_t LastUnique = 0;  ///< Counter for tracking unique names
 
 /// @}
 };
 
 } // end namespace llvm
 
 #endif // LLVM_IR_VALUESYMBOLTABLE_H

llvm/lib/IR/Function.cpp

 #include "llvm/IR/Operator.h"
 #include "llvm/IR/SymbolTableListTraits.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <cstring>
 #include <string>
 
 using namespace llvm;
 using ProfileCount = Function::ProfileCount;
 
 // Explicit instantiations of SymbolTableListTraits since some of the methods
 // are not in the public header file...
 template class llvm::SymbolTableListTraits<BasicBlock>;
 
+static cl::opt<unsigned> NonGlobalValueMaxNameSize(
+    "non-global-value-max-name-size", cl::Hidden, cl::init(1024),
+    cl::desc("Maximum size for the name of non-global values."));
+
 //===----------------------------------------------------------------------===//
 // Argument Implementation
 //===----------------------------------------------------------------------===//
 
 Argument::Argument(Type *Ty, const Twine &Name, Function *Par, unsigned ArgNo)
     : Value(Ty, Value::ArgumentVal), Parent(Par), ArgNo(ArgNo) {
   setName(Name);
 }
: GlobalObject(Ty, Value::FunctionVal,
                    computeAddrSpace(AddrSpace, ParentModule)),
       NumArgs(Ty->getNumParams()) {
   assert(FunctionType::isValidReturnType(getReturnType()) &&
          "invalid return type");
   setGlobalObjectSubClassData(0);
 
   // We only need a symbol table for a function if the context keeps value names
   if (!getContext().shouldDiscardValueNames())
-    SymTab = std::make_unique<ValueSymbolTable>();
+    SymTab = std::make_unique<ValueSymbolTable>(NonGlobalValueMaxNameSize);
 
   // If the function has arguments, mark them as lazily built.
   if (Ty->getNumParams())
     setValueSubclassData(1);   // Set the "has lazy arguments" bit.
 
   if (ParentModule)
     ParentModule->getFunctionList().push_back(this);
 

llvm/lib/IR/Module.cpp

 template class llvm::SymbolTableListTraits<GlobalAlias>;
 template class llvm::SymbolTableListTraits<GlobalIFunc>;
 
 //===----------------------------------------------------------------------===//
 // Primitive Module methods.
 //
 
 Module::Module(StringRef MID, LLVMContext &C)
-    : Context(C), ValSymTab(std::make_unique<ValueSymbolTable>()),
+    : Context(C), ValSymTab(std::make_unique<ValueSymbolTable>(0)),
       Materializer(), ModuleID(std::string(MID)),
       SourceFileName(std::string(MID)), DL("") {
   Context.addModule(this);
 }
 
 Module::~Module() {
   Context.removeModule(this);
   dropAllReferences();

llvm/lib/IR/Value.cpp

 #include <algorithm>
 
 using namespace llvm;
 
 static cl::opt<unsigned> UseDerefAtPointSemantics(
     "use-dereferenceable-at-point-semantics", cl::Hidden, cl::init(false),
     cl::desc("Deref attributes and metadata infer facts at definition only"));
 
-
-static cl::opt<unsigned> NonGlobalValueMaxNameSize(
-    "non-global-value-max-name-size", cl::Hidden, cl::init(1024),
-    cl::desc("Maximum size for the name of non-global values."));
-
 //===----------------------------------------------------------------------===//
 //                                Value Class
 //===----------------------------------------------------------------------===//
 static inline Type *checkType(Type *Ty) {
   assert(Ty && "Value defined with a null type: Error!");
   return Ty;
 }
 
void Value::setNameImpl(const Twine &NewName) {
   StringRef NameRef = NewName.toStringRef(NameData);
   assert(NameRef.find_first_of(0) == StringRef::npos &&
          "Null bytes are not allowed in names");
 
   // Name isn't changing?
   if (getName() == NameRef)
     return;
 
-  // Cap the size of non-GlobalValue names.
-  if (NameRef.size() > NonGlobalValueMaxNameSize && !isa<GlobalValue>(this))
-    NameRef =
-        NameRef.substr(0, std::max(1u, (unsigned)NonGlobalValueMaxNameSize));
-
   assert(!getType()->isVoidTy() && "Cannot assign a name to void values!");
 
   // Get the symbol table to update for this object.
   ValueSymbolTable *ST;
   if (getSymTab(this, ST))
     return;  // Cannot set a name on this value (e.g. constant).
 
   if (!ST) { // No symbol table to update?  Just do the change.

llvm/lib/IR/ValueSymbolTable.cpp

void ValueSymbolTable::removeValueName(ValueName *V) {
   // Remove the value from the symbol table.
   vmap.remove(V);
 }
 
 /// createValueName - This method attempts to create a value name and insert
 /// it into the symbol table with the specified name.  If it conflicts, it
 /// auto-renames the name and returns that instead.
 ValueName *ValueSymbolTable::createValueName(StringRef Name, Value *V) {
+  if (maxNameSize > 0 && Name.size() > maxNameSize)
+    Name = Name.substr(0, std::max(1u, maxNameSize));
+
   // In the common case, the name is not already in the symbol table.
   auto IterBool = vmap.insert(std::make_pair(Name, V));
   if (IterBool.second) {
     // LLVM_DEBUG(dbgs() << " Inserted value: " << Entry.getKeyData() << ": "
     //           << *V << "\n");
     return &*IterBool.first;
   }
 

llvm/test/Assembler/non-global-value-max-name-size.ll

+; RUN: opt < %s -S -non-global-value-max-name-size=4
+; Test that local value name lookup works if the name is capped
+
+define void @f() {
+bb0:
+  br label %testz
+
+testz:
+  br label %testz
+}