This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by hasyimibhar on May 18 2021, 11:30 AM.

Details

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.

Diff Detail

Event Timeline

hasyimibhar created this revision.May 18 2021, 11:30 AM
hasyimibhar requested review of this revision.May 18 2021, 11:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 18 2021, 11:30 AM

Remove whitespace

hasyimibhar edited the summary of this revision. (Show Details)

Add description to test

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 edited reviewers, added: hfinkel, chandlerc; removed: uabelho.May 18 2021, 9:02 PM

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

mehdi_amini added inline comments.
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 updated this revision to Diff 346351.EditedMay 19 2021, 12:15 AM

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).

Remove duplicate code

hasyimibhar marked 2 inline comments as done.May 19 2021, 12:21 AM
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 added inline comments.May 19 2021, 3:15 AM
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.

Fix clang-tidy error

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?

Move call of capLocalValueName into ValueSymbolTable

hasyimibhar added inline comments.May 19 2021, 10:15 AM
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 added inline comments.May 19 2021, 3:47 PM
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 updated this revision to Diff 346652.EditedMay 20 2021, 1:22 AM

Move capping to ValueSymbolTable

hasyimibhar added inline comments.May 20 2021, 1:27 AM
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.

Fix clang-tidy error

hasyimibhar edited the summary of this revision. (Show Details)May 20 2021, 4:15 AM
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 added inline comments.May 21 2021, 1:37 PM
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.

Add LocalValueSymbolTable

Run clang-format

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

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 added inline comments.May 22 2021, 9:32 AM
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?).

Add isLocal to ValueSymbolTable to differentiate usage

hasyimibhar added inline comments.May 23 2021, 7:26 AM
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.

Use maxNameSize argument in constructor

mehdi_amini added inline comments.May 23 2021, 10:04 AM
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 added inline comments.May 23 2021, 2:59 PM
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.

Use int for maxNameSize

hasyimibhar added inline comments.May 23 2021, 3:01 PM
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.

Fix clang-tidy error

mehdi_amini accepted this revision.May 25 2021, 11:20 AM
mehdi_amini added inline comments.
llvm/include/llvm/IR/ValueSymbolTable.h
75–80

Ah my bad, I missed this somehow!

This revision is now accepted and ready to land.May 25 2021, 11:20 AM

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 added a subscriber: dim.Jan 24 2022, 12:41 PM

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? :)

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 added a comment.Jan 24 2022, 3:09 PM

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 added a comment.Jan 25 2022, 8:56 AM

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 added a comment.Jan 25 2022, 9:59 AM

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

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

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 added a comment.Jan 27 2022, 12:23 PM

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.