I will let @davide to decide. I will talk to him offline if he didn't reply here. Looking at the libLTO shipped by Apple, it actually have more symbols than listed here so it could be reasonable just keep the minimal list of symbols intended here.

In D143229#4103367, @aeubanks wrote:

In D143229#4103364, @steven_wu wrote:

In D143229#4103332, @aeubanks wrote:

check llvm.ident instead

If my source module is bitcode upgraded, it won't get a new llvm.ident right? Then the upgrade pass will be wrongly skipped. I think we need a LLVM code generator version somewhere in the IR

it the bitcode was upgraded, then during the upgrade it should already have had UpgradeDebugInfo called on it (with the expected LLVM revision) right?

In D143229#4103332, @aeubanks wrote:

check llvm.ident instead

I don't think this restriction works for Apple. Compatibility is important for users that needs external dependencies that they do not control. If the debug info upgrader is expensive for you, we can probably add a fast check to skip that, or just give user a flag to control that behavior.

@MaskRay Those disassembler symbols are actually used by otool, see: https://opensource.apple.com/source/cctools/cctools-973.0.1/otool/arm_disasm.c.auto.html

In D141625#4100790, @dblaikie wrote:

In D141625#4100762, @steven_wu wrote:

I don't think it is feasible with current tool to write a test that check semantically the order of decls in clang module. (Let me know if that was wrong). The current test already unfortunately relies on the module layout assuming op13 is the field for anonymous declaration number.

Sure enough - having these things have semantic identifiers rather than numbers would help.

Ah, perhaps I'm just confused - I'm not sure why a similar test, that tested a different order of the op13 fields wouldn't've shown a failure without reverse iteration and then failed with reverse iteration (or the other way around) - and then could be updated with a different ordering with the fix.

Sorry, I'm clearly not making much sense here. Yes, I think the test should be reduced further (while still showing the failure in either forward or reverse iteration - but, yes, losing coverage in the real world rehashing situation) it'd make the test shorter and more maintainable (to @akyrtzi's point about future changes that introduce benign reordering) but it's not the worst example of long tests to tickle hash instability. *shrug*

I'm not insisting on it/blocking this patch from going forward without addressing this issue. Carry on.

I don't think it is feasible with current tool to write a test that check semantically the order of decls in clang module. (Let me know if that was wrong). The current test already unfortunately relies on the module layout assuming op13 is the field for anonymous declaration number. Adding more dependency on the exact layout of the clang module will make the test really fragile to any clang AST change.

Sorry, I'm still not really following - OK, sounds like you're saying this test does fail at HEAD/without this patch in reverse iteration mode, and is a bit larger than would be minimally necessary to achieve that, but also might fail at HEAD without reverse iteration, providing somewhat more testing than if it were fully minimized/only caught in reverse.

Fair enough -I don't think it's the right tradeoff, but I'm glad it's stable/provides that coverage.

Try fix pre-merge build failure

In D141625#4094837, @dblaikie wrote:

In D141625#4094742, @steven_wu wrote:

In D141625#4067225, @dblaikie wrote:

In D141625#4066961, @steven_wu wrote:

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same.

Hmm, I'm not sure I'm following why that is - could you explain this in more detail? The usual problem is that, say, we're outputting based on an unstable order - even two items would be enough to cause a test of that to fail in either forward or reverse iteration mode until the order is stabilized.

Is that not the case here? Is there some interaction between iteration order that's part of the nondeterminism here?

In order to make a test that will break before the change with reverse iteration, the test needs to check that the decls/records are serialized into the module in a pre deterministic order. It can't be just diff the output of two runs with a small input because small input will not overflow the smallptrset, thus the reverse iteration outputs from two runs will very likely to be identical, just in a different order from forward iteration.

Sure, I think I'm with you there - but the current test checks that the decls/records are serialized into the module in a pre-deterministic order, right? So it doesn't seem like a reverse iteration-failing test would be more involved/brittle/less robust than the test being added here?

Rebase to main.

In D141625#4067225, @dblaikie wrote:

In D141625#4066961, @steven_wu wrote:

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same.

Hmm, I'm not sure I'm following why that is - could you explain this in more detail? The usual problem is that, say, we're outputting based on an unstable order - even two items would be enough to cause a test of that to fail in either forward or reverse iteration mode until the order is stabilized.

Is that not the case here? Is there some interaction between iteration order that's part of the nondeterminism here?

I think this violates a core tenet of being a modular, reusable IR. It shouldn't be wrong to run a pass twice. It certainly shouldn't error by way of verifier error

I am not the expert to answer that question. I will think this is an assertion-like behavior. It tells you as a compiler developer that your pipeline configuration is wrong in a sense that you should add all the functions in before running post link passes. You should delay the post link pass when you hit this error, rather than disable the check without a compelling reason.

My understanding of the flag is preventing you from:

• run the devirtual pass
• add some new function
• run the devirtual pass again

I agree that this probably doesn't work for CAS since the use of CAS is not bounded to any context like a ThreadPoolExecutor, for example, it is currently a legal use case to have multiple thread pool to insert into CAS at the same time. It is not feasible to put such a restriction on CAS since CAS should be safe to read/write concurrently from different process.

In D136315#4069849, @calebzulawski wrote:

In my situation, at least, I am the vendor of the toolchain and my configuration file contains --sysroot=<CFGDIR>/../path/to/sysroot with a known relative path to where the sysroot is distributed. Apple is unique in this situation, since I am not distributing the sysroot, so there is no equivalent to using the <CFGDIR> variable. There is no way to invoke xcrun or set SDKROOT from config files, only pass flags.

It is true that the build system could do it, but I think it's reasonable for the driver to make a guess when not provided. I don't think it's all that different than detection of libstdc++ from GCC installs.

Ping. Rebase the file on main

This is not an apple platform problem. This is a cross compile problem where you have a SDK that is installed for cross compile target. In those cases, you just can't hard code the path to isysroot, and figuring out the sysroot is generally considered a problem for the build system, not the problem for compiler. If you have a config file, you can definitely setup SDKROOT in your configuration system after running xcrun. A similar but not identical problem is if you just install clang package but didn't install dev packages on a linux platform where you just can't find any headers. Same error, just different causes.

In D136315#4069582, @calebzulawski wrote:

That makes more sense, I thought perhaps it was using DEFAULT_SYSROOT. The shim isn't smart enough to choose the sysroot from the target unfortunately.

It looks like the only error is unrelated to this change, something with concepts in libc++.

In D136315#4067205, @calebzulawski wrote:

One thing to throw into the mix: Apple's clang has a default sysroot configured, so with the default system compiler, there is no way to replicate this "build without a sysroot" scenario as far as I can tell. For the system compiler, I believe this behavior is a strict improvement.

No, reverse iteration will not break diff test for a small number of decls. Everything will be in reverse order so it is the same. Current test will fail early in reverse iteration and will fail in the end statistically for forward iteration. Will pass in all configurations. I think paying a bit more decls to make it fail in forward iteration is not a bad trade off.

This breaks macOS bot too: https://green.lab.llvm.org/green/job/clang-stage1-cmake-RA-incremental/33839/

Update tests according to feedback

In D141625#4066466, @dblaikie wrote:

In D141625#4066362, @steven_wu wrote:

@dblaikie Do you have any objection for committing the patch as it is? I don't think reverse iteration test is a proper way to test for this specific bug.

I think reverse iteration is the right way to test this specific bug (& any bug where behavior may be unintentionally nondeterministic due to non-deterministically ordered containers) - it makes the testing more reliable rather than depending on implementation details of such containers that aren't guaranteed (that being the point/problem).

But it's not the worst/most unwieldy test for this sort of thing & if we don't have bots using it... hmm, actually I looked more closely & maybe we do have reverse iteration builders: https://github.com/llvm/llvm-zorg/search?q=reverse-iteration (though I'm having trouble navigating the builder UI to see whether there are up-to-date builds for this configuration)

Could you help me understand your perspective regarding using reverse iteration to test this specific bug? (are there some bugs you find reverse iteration suitable for? what's different about this one from them?)

@dblaikie Do you have any objection for committing the patch as it is? I don't think reverse iteration test is a proper way to test for this specific bug.

In D141625#4060460, @dblaikie wrote:

In D141625#4059486, @steven_wu wrote:

@dblaikie Do we have any bots running reverse iteration?

Hmm, not that I can see/find at a quick glance, which is unfortunate. @mgrang Are you still working on LLVM/have any knowledge of reverse iteration testing being done? (@colinl - looks like maybe you're a Code Aurora person, perhaps you've got some more recent context for this?)

Update after makeArrayRef depreciation.

Formatting and minor update.

In D141625#4059540, @tschuett wrote:

EXPANSIVE_CHECKS will reshuffle the llvm::sort input: https://lists.llvm.org/pipermail/llvm-dev/2018-April/122576.html

Address review feedback

Update after makeArrayRef deprecation

@dblaikie Do we have any bots running reverse iteration?

In D141625#4056831, @steven_wu wrote:

Actually, sorting in numberAnonymousDeclsWithin doesn't work for some reasons.

Actually, sorting in numberAnonymousDeclsWithin doesn't work for some reasons.

Minor touch up on the test case. Also add some comments in test to explain what is being tested.

@akyrtzi has the good idea. It is really hard to control Decl* to get values
to get an unstable iteration order from the small tests, going beyond 32 decls
to get out of SmallPtrSet's small model is much consistent.

In D141625#4052869, @rsmith wrote:

In D141625#4052820, @dblaikie wrote:

Yeah, might be nice to document where the instability comes from - if it comes from a DenseMap or similar, then a test that fails either in forward or reverse iteration mode would be nice to have.

Scope::decls is iterating over a SmallPtrSet. This might be a little annoying to create a test for, because it'll only be unstable if we have two decls in the same prototype scope that get allocated into different slabs by the bump ptr allocator, but maybe something like:

void f(struct A *p, int arr[1 + 0 + 0 + 0 + ... + 0], struct B *q);

... would be enough (with sufficient subexpressions to fill a whole slab). Then we can build a .pch for that twice and check that it comes out identical.

Update unittest:

Address review feedback. Remove NFC from title.

Update patch after HashMap rename

Rename to TrieRawHashMap.

Maybe RawHashTrieMap? It reads better when Raw is in the front, and it contains hash-trie and trie-map, which are both terms describing data structures similar to this but this is much simpler, thus raw.

@dexonsmith @benlangmuir @akyrtzi
Does TrieHashMap sound good to you?

Minor format and test update

Update unittest to wait and check.

@dexonsmith Move the discussion here.

In D133715#4031396, @avl wrote:

But having a fast concurrent BumpPtrAllocator would be independently useful, and I'd suggest optimizing the allocator before bloating the default trie size.

+1 for fast concurrent ThreadSafeBumpPtrAllocator.

What do you think about following alternative implementation?

class ThreadSafeBumpPtrAllocator {
  ThreadSafeBumpPtrAllocator() {
    size_t ThreadsNum = ThreadPoolStrategy.compute_thread_count();
    allocators.resize(ThreadsNum);
  }
  
  void* Allocate (size_t Num) {
      size_t AllocatorIdx = getThreadIdx();
      
      return allocators[AllocatorIdx].Allocate(Num);
  }

  std::vector<BumpPtrAllocator> allocators;
};

static thread_local ThreadIdx;

size_t getThreadIdx() {
  return ThreadIdx;
}

This implementation uses the fact that ThreadPoolExecutor creates a fixed number
of threads(ThreadPoolStrategy.compute_thread_count()) and keeps them until destructed
. ThreadPoolExecutor can initialise thread local field ThreadIdx to the proper thread index.
The getThreadIdx() could return index of thread inside ThreadPoolExecutor.Threads.
ThreadSafeBumpPtrAllocator keeps separate allocator for each thread. In this case each thread would
always use separate allocator. No neccessary to have locks, cas operations, no races...

Add docs in the reference page that address CAS in different prespective.

In D133715#4029841, @dexonsmith wrote:

In D133715#4029442, @steven_wu wrote:

Ping. All feedbacks are addressed.

Additional notes: I dig a bit deeper into the benchmark from https://reviews.llvm.org/D132548 as it shows bad scaling during parallel insertion tests (stop scaling to 8 threads). That is actually caused by our ThreadSafeBumpPtrAllocator that currently takes a lock. We can improve it in future since our use case doesn't expect heavy parallel insertions. However, it is quite obvious we should tune to RootBits and SubTrieBits. Increasing RootBits can significantly decrease the contention. A better strategy might be something like starting with something like 10 bits, then 4 bits, 2 bits and 1 bit. Shrinking number of bits can lead to better memory usage since the slots usage in the deep nodes are very low.

Could ThreadSafeBumpPtrAllocator could be made lock-free? I think at least it would be possible to implement one that only locked when a new allocation is needed, instead of every time the ptr is bumped as now. (I’ll think about it a bit.)

Note that in the CAS use case it’s ideally true that most insertions are duplicates and don’t need to call the allocator at all. This is why we’ve been able to get away with a lock on each allocation.

The ability to dump the data structure I'm all for - like DenseMap, etc, but I think that dumping should be the user-visible state (it's a map, the trie part is an implementation detail that ideally shouldn't be exposed in the dump developers use regularly - presumably it's not necessary except when debugging the data structure itself, which should be rare (we don't usually need to look at DenseMap's internal bucketing, for instance)).

Fix non-assert build test

Address review feedback

Ping. All feedbacks are addressed.

Allow checking prefix of the sub-trie

Fix typo in the comments

Update tests to avoid string comparsion.

In D132455#4026480, @avl wrote:

I am super interested in how you do the comparison. Can you post a patch for the code you have for that? The HashMappedTrie hasn't been really tuned for performance/memory usage, it would be interesting to use your tool to do some investigation (for example, the NumRootBits and NumSubtrieBits can be tuned for memory/performance).

@steven_wu I`ve updated D132548 to have a possibility to measure HashMappedTrie. It depends on D125979, D132455, D133715.
In its current state patch does not set NumRootBits, NumSubtrieBits, though such options might be added.
If intel threading building block hashmap is not neccessary - the USE_ITBB should be unset.
if lib cuckoo hashmap is not neccessary - the USE_LIBCUCKOO should be unset.
Command line to run the tool:

/usr/bin/time -f " %E %M " ./check-hashtable --data-set random --num-threads 1 --table-kind hash-mapped-trie --aggregate-data

Any changes/suggestions are welcomed :-)

Add some documentation about HashMappedTrie

Rebase for std::optional

Address review feedback and rebase the patch using std::optional

In D133715#3996263, @dblaikie wrote:

In D133715#3996194, @dexonsmith wrote:

In D133715#3996103, @dblaikie wrote:

eh, maybe string's easier to read in expect diagnostics anyway... just seems a bit awkward/circuitous/unfortunate :/ (I guess the stringification could move into the test code, implemented via such a friend relationship)

I do remember the string being easy to read in expect diagnostics, FWIW.

What about renaming the methods to printLayout() and dumpLayout()? Then print() and dump() would at least still be available for something user-centric.

Workable, though I'd still rather it be moved to the test file if it's not too inconvenient (with some friendship, probably). Avoid muddying the implementation with test-only features.

Thanks for doing the comparison with https://reviews.llvm.org/D133715.

In D139938#4008232, @hans wrote:

This seems to have broken the instrprof-darwin-exports.c test, see e.g. https://green.lab.llvm.org/green/job/clang-stage1-RA/32351/

I'll revert for now.

Also needed a follow up fix to completely fix module 9cd6fbee7ed8

Fix typo

LGTM

This breaks llvm/example:

/Users/buildslave/jenkins/workspace/clang-stage1-cmake-RA-incremental/llvm-project/llvm/examples/ModuleMaker/ModuleMaker.cpp:58:7: error: 'getInstList' is a private member of 'llvm::BasicBlock'

See: https://green.lab.llvm.org/green/job/clang-stage1-cmake-RA-incremental/33265/console

In D133715#3995988, @dexonsmith wrote:

In D133715#3995750, @dblaikie wrote:

In D133715#3993521, @dexonsmith wrote:

In D133715#3993489, @dblaikie wrote:

• a test support friend class that can inspect/test the trie layout without relying on stringification;

This bit I'm not so sure about - we don't test the bucketing behavior of DenseHashMap so far as I know (or other similar implementation details of the various other hashing data structures - (since they're the ones with fairly complicated implementation details, they seem the best comparison)), for instance, we only test its interface - why would we do differently for this data structure?

IMO the layout is more complex than a flat array with quadratic probing. The logic for equal and/or nearly-equal hashes is a bit subtle, and there were hard-to-reason about bugs originally. The layout-stringification was necessary to understand what was going wrong, and the tests that use it help ensure future refactorings don't get it wrong.

I don't remember the bugs, but two examples of subtleties:

• On an exact match you don't want to "sink" the existing entry down a level to a new sub-trie (you need to detect "exact match" before sinking). Getting this wrong will affect performance but not otherwise be user-visible.
• The deepest sub-trie might be a different/smaller size than the others because there are only a few bits left-over, and the handling needs to be right. It's simpler to check for correct layout directly than to guess about what user-visible effects there might be for errors.

I'd be a bit uneasy with the layout tests being dropped altogether.

Maybe an alternative to testing the layout directly would be to add a verification member function that iterated through the data structure and ensured everything was self-consistent (else crash? else return false?). Then the tests could call the member function after a series of insertions that might trigger a "bad" layout.

Fair enough - if it's sufficient to have a verify operation (maybe "assertValid" - so, yeah, crash when not valid) I'd go with that, but given the argument you've made, if you think verifying the specific structure is significantly more valuable than that, I'd be OK with some private/test-friended introspection API.

IMO it's worth it; @steven_wu, if you disagree, I could live with assertValid(). (BTW, I remembered another justification. The test case inputs/setups are a bit subtle; checking the layout ensures you've covered the corner case you think you've covered.)

The workaround in https://reviews.llvm.org/D139956 can get llvm-project bootstrap correctly, doesn't fix the underlying issue.

LGTM